HDU 3756 Dome of Circus

时间:2022-07-10 17:20:36

不会做,参见别人的程序:

/*
底面为xy平面和轴为z轴的圆锥,给定一些点,使得圆锥覆盖所有点并且体积最小
点都可以投射到xz平面,问题转换为确定一条直线(交x,z与正半轴)使得与x的截距r
和与z轴的截距h满足h*r*r最小。
三分,对于确定的h可以找到最佳的r,并且h*r*r的曲线必定只有一个极小值
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct po
{
double x,y;
}p[];
const double eps=1e-;
double Y;
int n;
double makeR(double h)
{
double R=;
for(int i=;i<n;i++)
{
if(R*(h-p[i].y)<h*p[i].x)
R=h*p[i].x/(h-p[i].y);
}
return R;
}
void solve()
{
double L=Y,R=<<,tmp;
while(R-L>eps)
{
tmp=(R-L)/3.0;
double mid1=L+tmp;
double mid2=L+2.0*tmp;
double R1=makeR(mid1);
double R2=makeR(mid2);
if(R1*R1*mid1>R2*R2*mid2)
{
L=mid1;
}
else
{
R=mid2;
}
}
printf("%.3lf %.3lf\n",L+eps,makeR(L)+eps);
}
int main()
{
int i,j,k;
int ca;
scanf("%d",&ca);
while(ca--)
{
scanf("%d",&n);
double tx,ty,Left=;
Y=;
for(i=;i<n;i++)
{
scanf("%lf%lf%lf",&tx,&ty,&p[i].y);
p[i].x=sqrt(tx*tx+ty*ty);
Y=max(p[i].y,Y);
}
solve();
}
return ;
}