原题大意

在一个三维空间里，已知有N个点，求一个最小的圆锥使所有的点都包含其中。

算法分析

试着只考虑一个点。
R的最小值和H之间有，形如R=k*H+b的关系。
令高度为H时体积最小值为f(H)，便会发现f(H)是单峰的
考虑所有的点，那么高度为H时体积最小值为 max{f(H)}，
归纳得，很多个单峰函数取max后仍是单峰函数
所以就可以三分答案了。
三分可以用来求出凸或凹函数的最值。

http://blog.csdn.net/pi9nc/article/details/9666627

程序代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 10005;
const double EPS = 1e-4;
int T, n;
double x[maxn], y[maxn], z[maxn];
double f(double h){
    double r = 0.0;
    for(int i = 0; i < n; i++)
    {
        r = max(r, h*x[i]/(h-y[i]));//相似三角形的性质
    }
    return h*r*r;
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        double L = 0, R = 1e9;
        for(int i = 0; i < n; i++)
        {
            scanf("%lf %lf %lf", &x[i], &y[i], &z[i]);
            x[i] = sqrt(x[i] * x[i] + y[i] * y[i]);//将点投影到xz面上
            y[i] = z[i];//y记录高度h
            L = max(L, y[i]);//三分的左端点
        }
        L += EPS;
        //三分
        for(int i = 1; i <= 100; i++)
        {
            double mid_L = (L + R) /2;
            double mid_R = (mid_L + R) /2;
            if(f(mid_L) > f(mid_R))
                L = mid_L;
            else
                R = mid_R;
        }
        printf("%.3lf %.3lf\n", L, sqrt(f(L)/L));
    }
    return 0;
}