PKU 3962 Dome of Circus
http://poj.org/problem?id=3962
原点を中心として、n個の点を含む円錐形のテントを貼りたい。
このとき、点の座標が与えられるので、テントの体積が最も小さくなるときのテントの半径と高さを答えろというような問題。
テントの側面の角度で三分探索。
入力は多いよう。
pair<double,double> in[10000]; main(){ int n; scanf("%d",&n); rep(i,n){ double x,y,z; scanf("%lf%lf%lf",&x,&y,&z); in[i]=mp(sqrt(x*x+y*y),z); } double Vu=1LL<<40,Vl=1LL<<40; double l=0,u=pi/2; double r1=0,r2=0; while(abs(l-u)>1e-8){ double mid1=(2*l+u)/3; double mid2=(l+2*u)/3; r1=0; r2=0; double tanth1=tan(mid1); double tanth2=tan(mid2); rep(i,n){ r1=max(r1,in[i].F+in[i].S/tanth1); r2=max(r2,in[i].F+in[i].S/tanth2); } double tv1=r1*r1*r1*tanth1; double tv2=r2*r2*r2*tanth2; if(tv1<tv2){ Vu=tv2; u=mid2; }else{ Vl=tv1; l=mid1; } } printf("%.3f %.3f\n",r1*tan(l),r1); }