UVA 1473 - Dome of Circus(三分+计算几何)

这题先推下公式，很容易发现圆锥的体积和半径满足一个二次函数，所以可以用三分

于是三分半径即可

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 10005;
const double PI = acos(-1.0);

struct Point {
    double x, y, z;
    void read() {
        scanf("%lf%lf%lf", &x, &y, &z);
    }
} p[N];

int n;

double gao(double r) {
    double h = 0;
    for (int i = 0; i < n; i++) {
        double d = sqrt(p[i].x * p[i].x + p[i].y * p[i].y);
        h = max(h, p[i].z / (r - d) * r);
    }
    return h;
}

int main() {
    while (~scanf("%d", &n)) {
        double l = 0, r = 1e20;
        for (int i = 0; i < n; i++) {
            p[i].read();
            l = max(l, sqrt(p[i].x * p[i].x + p[i].y * p[i].y));
        }
        l += 1e-8;
        for (int i = 0; i < 200; i++) {
            double midl = (l * 2 + r) / 3;
            double midr = (l + r * 2) / 3;
            double h1 = gao(midl);
            double h2 = gao(midr);
            double s1 = PI * midl / 3 * midl * h1;
            double s2 = PI * midr / 3 * midr * h2;
            if (s1 > s2) l = midl;
            else r = midr;
        }
        printf("%.3f %.3f\n", gao(l), l);
    }
    return 0;
}

UVA 1473 - Dome of Circus(三分+计算几何)

原文：http://blog.csdn.net/accelerator_/article/details/44650551