【题意】：在三维空间中，给出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 }