UVA Live 4986：最小體積圓錐包裹空間點——三分查找解法

問題描述

給定空間中 n 個點（z ≥ 0），求一個底面圓心在原點 (0,0) 的圓錐，包裹所有點且體積最小。輸出該圓錐的高 h 與底面半徑 r。

圓錐體積公式：V = 1/3 * π * r² * h。對於固定 h，r 由最遠點決定；V 作為 h 的函數呈凸性，可用三分查找求極值。

幾何關係推導

將三維問題投影到二維：點 (x, y, z) → 極坐標距離 d = sqrt(x² + y²) 與高度 z。圓錐邊界線通過 (0, h) 和 (r, 0)，方程為 z = h - (h/r) * d。點 (d, z) 在圓錐內滿足 z ≤ h - (h/r) * d，解得所需最小 r：

r = max( d_i * h / (h - z_i) )，對所有點 i 取最大值。

三分查找演算法

1. 搜索區間：l = max(z_i)（高至少大於最高點），r = 1e9（足夠大）。
2. 每次取兩個中間點 h1 = (l+r)/2, h2 = (h1+r)/2。
3. 計算對應體積 V1 = r1² * h1, V2 = r2² * h2（忽略常數 1/3π）。
4. 若 V1 < V2，最小值在左側，r = h2；否則 l = h1。
5. 迭代直到區間足夠小（如 1e-9）。

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1), EPS = 1e-9;
struct Point { double x, y; }; // x: 水平距離 d, y: 高度 z
Point P[10005];
int n;

int dcmp(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); }

double solve(double h) { // 給定 h 計算最小 r
    double r = -1;
    for (int i = 0; i < n; ++i)
        if (dcmp(h - P[i].y) > 0) // h > z_i
            r = max(r, P[i].x * h / (h - P[i].y));
    return r;
}

int main() {
    while (scanf("%d", &n) == 1) {
        double l = 0, r = 1e9;
        for (int i = 0; i < n; ++i) {
            double x, y, z; scanf("%lf%lf%lf", &x, &y, &z);
            P[i].x = sqrt(x*x + y*y); P[i].y = z;
            l = max(l, z);
        }
        while (dcmp(r - l) > 0) {
            double h1 = (l + r) / 2, h2 = (h1 + r) / 2;
            double r1 = solve(h1), r2 = solve(h2);
            if (r1*r1*h1 < r2*r2*h2) r = h2;
            else l = h1;
        }
        printf("%.3lf %.3lf\n", l, solve(l));
    }
    return 0;
}

關鍵點總結

• 利用凸函數單峰性質，三分查找高度 h。
• 幾何轉換將 3D 問題簡化為 2D 邊界線計算。
• 精度控制用 dcmp 處理浮點數比較。