【題意】：在三維空間中，給出n個點(x,y,z) (z>=0)，要求用一個體積最小的圓錐包圍所有的點，輸出該圓錐的高和半徑。
【題解】：可以先分析一下，當這個圓錐的高很大時，圓錐的體積非常大；當這個圓錐的高太小的時候，圓錐的半徑就會非常大，此時圓錐的體積還是很大。
于是我們可以得出一個結論，圓錐的高不能太小也不能太大。
這里有一步預處理，就是把空間直角坐標系轉換為柱面坐標系。(x,y,z) => (sqrt(x*x+y*y),z);
有了上面的結論，我們就可以利用三分極值來確定這個高的最優值，然后通過相似三角形就可以求出圓錐的半徑。
此題也可以通過三分半徑來求解。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "cmath"
5 using namespace std;
6 #define maxn 10500
7 #define eps 1e-8
8 #define pi 3.1415926535897932384626433832795
9 int n;
10 double rr;
11 struct Point {
12 double x, y, r, z;
13 Point(){}
14 Point(double _x, double _y, double _z) {
15 x = _x, y = _y, z = _z, r = sqrt(_x * _x + _y * _y) ;
16 }
17 }point[maxn];
18
19 double work(double h) {
20 double tmp;
21 rr = 0.0;
22 for(int i = 0; i < n; i++) {
23 double r = point[i].r, z = point[i].z;
24 double tmp = h * r / (h - z);
25 rr = max(rr, tmp);
26 }
27 double area = pi * rr * rr * h / 3.0;
28 return area;
29 }
30
31 void solve(double res) {
32 double low = res, high = 10000000, mid, mmid, ansh, ansr;
33 while(low + eps < high) {
34 mid = (low + high) / 2.0;
35 mmid = (mid + high) / 2.0;
36 if(work(mid) < work(mmid)) {
37 high = mmid;
38 ansh = mid;
39 } else {
40 low = mid;
41 ansh = mmid;
42 }
43 ansr = rr;
44 }
45 printf("%.3f %.3f\n", ansh, ansr);
46
47 }
48
49 int main() {
50 int T;
51 double x, y, z;
52 scanf("%d", &T);
53 while(T--) {
54 scanf("%d", &n);
55 double low = 0.0;
56 for(int i = 0; i < n; i++) {
57 scanf("%lf%lf%lf", &x, &y, &z);
58 point[i] = Point(x, y, z);
59 low = max(low, z);
60 }
61 solve(low);
62 }
63 return 0;
64 }