题意：给出空间内一些Z>0的点，保证有点不在Z轴上，求一个体积最小的包含所有点的圆锥，输出其h和r。
思路：基本所有人都能想到二维化，问题就转化成了在第一象限内有一些y>0的点，用一条斜率<0的直线覆盖它们。很容易证明最优解的直线应该过其中一个或两个点，再推算一下可以得出，过点(x,y)的最优解为r = 1.5x，h = 3y，越接近它V越小。这样问题就简单明了了，先做一个凸包，再找出上凸包中斜率<0的边所过的点，枚举这些点的最优解就行了。
做这题时WA了好几发，害得我以为是精度问题，后来才知道，是INF开小了（╯' - ')╯ ┻━┻ （掀桌子）。于是我把所有涉及精度的部分全还原了┬—┬ ノ( ' - 'ノ) （摆好摆好），发现跑出来时间还是242ms，(╯°Д°)╯ ┻━┻（再他妈的掀一次)。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 #define N 10010 6 struct Point{ 7 double x, y; 8 Point(double _x = 0, double _y = 0):x(_x), y(_y){} 9 Point operator-(const Point &P)const{ return Point(x-P.x, y-P.y); } 10 bool operator< (const Point &p)const{ return (x<p.x||(x==p.x&&y<p.y)); } 11 }; 12 double Cross(const Point &A, const Point &B){ return A.x*B.y-A.y*B.x; } 13 Point p[N],ch[N]; 14 double a[N]; 15 double getx(Point A, Point B){ 16 return (A.x*B.y-B.x*A.y)/(B.y-A.y); 17 } 18 double gety(Point A, Point B){ 19 return (A.x*B.y-B.x*A.y)/(A.x-B.x); 20 } 21 int main(){ 22 int n,m,k,i; 23 double x,y,z; 24 while(~scanf("%d",&n)){ 25 for(i = 0; i < n; i++){ 26 scanf("%lf%lf%lf",&x,&y,&z); 27 p[i].x = sqrt(x*x+y*y); 28 p[i].y = z; 29 } 30 sort(p,p+n); 31 m = 0; 32 for(i = 0; i < n; i++){ 33 while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <= 0) m--; 34 ch[m++] = p[i]; 35 } 36 k = m; 37 for(i = n-2; i >= 0; i--){ 38 while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <= 0) m--; 39 ch[m++] = p[i]; 40 } 41 if(n > 1) m--; 42 ch[m] = ch[0]; 43 double Min,r,h,R,H; 44 Min = 8000000000000000000.0; a[k-1] = ch[k-1].x; 45 for(i = k; i <= m; i++){ 46 if(ch[i].y <= ch[i-1].y) break; 47 a[i] = getx(ch[i],ch[i-1]); 48 if(1.5*ch[i-1].x < a[i-1]) 49 r = a[i-1], h = gety(ch[i-1],Point(r,0)); 50 else if(1.5*ch[i-1].x <= a[i]) 51 r = 1.5*ch[i-1].x, h = 3*ch[i-1].y; 52 else r = a[i], h = gety(ch[i-1],Point(r,0)); 53 if(r*r*h < Min){ 54 Min = r*r*h; 55 R = r; H = h; 56 } 57 } 58 if(1.5*ch[i-1].x < a[i-1]) 59 r = a[i-1], h = gety(ch[i-1],Point(r,0)); 60 else r = 1.5*ch[i-1].x, h = 3*ch[i-1].y; 61 if(r*r*h < Min){ 62 R = r; H = h; 63 } 64 printf("%.3lf %.3lf ",H,R); 65 } 66 return 0; 67 }