BZOJ 2823 AHOI 2012 信號塔：凸包 + 最小覆蓋圓

問題描述

平面 n 個點，求最小圓覆蓋所有點。輸出圓心坐標與半徑，保留兩位小數。

核心定理

最小覆蓋圓由凸包上的點決定（內部點不影響）。且最小覆蓋圓要么：
1. 由凸包上兩點為直徑決定
2. 由凸包上三點確定的圓決定（三角形外接圓）

算法流程

1. Andrew 算法求凸包 O(n log n)，得到頂點序列 ch
2. 枚舉凸包上所有三點組，計算外接圓圓心，檢查是否覆蓋所有凸包點
3. 枚舉所有兩點組，以兩點為直徑構造圓，檢查覆蓋
4. 取半徑最小的合法圓

三角形外接圓圓心公式

設三點 A(x₁,y₁), B(x₂,y₂), C(x₃,y₃)。
圓心 O(x,y)：
x = [ (x₁²+y₁²)(y₂-y₃) + (x₂²+y₂²)(y₃-y₁) + (x₃²+y₃²)(y₁-y₂) ] / D
y = [ (x₁²+y₁²)(x₃-x₂) + (x₂²+y₂²)(x₁-x₃) + (x₃²+y₃²)(x₂-x₁) ] / D
D = 2[ x₁(y₂-y₃) + x₂(y₃-y₁) + x₃(y₁-y₂) ]

完整代碼框架

#include 
using namespace std;
struct Point { double x,y; };
double cross(Point a, Point b, Point c) { return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); }

vector convexHull(vector p) {
    sort(p.begin(), p.end(), [](Point a, Point b){ return a.x!=b.x ? a.x ch(n+1);
    for (int i=0; i1 && cross(ch[m-2], ch[m-1], p[i]) <= 0) --m;
        ch[m++] = p[i];
    }
    int k=m;
    for (int i=n-2; i>=0; --i) {
        while (m>k && cross(ch[m-2], ch[m-1], p[i]) <= 0) --m;
        ch[m++] = p[i];
    }
    if (n>1) --m;
    ch.resize(m);
    return ch;
}

Point circumcenter(Point a, Point b, Point c) {
    double d = 2*(a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
    double ux = ((a.x*a.x+a.y*a.y)*(b.y-c.y) + (b.x*b.x+b.y*b.y)*(c.y-a.y) + (c.x*c.x+c.y*c.y)*(a.y-b.y)) / d;
    double uy = ((a.x*a.x+a.y*a.y)*(c.x-b.x) + (b.x*b.x+b.y*b.y)*(a.x-c.x) + (c.x*c.x+c.y*c.y)*(b.x-a.x)) / d;
    return {ux, uy};
}

bool covers(const vector& ch, Point o, double r) {
    for (auto& p : ch) if (dist(p, o) > r + 1e-9) return false;
    return true;
}

int main() {
    int n; cin >> n;
    vector p(n);
    for (auto& pt : p) cin >> pt.x >> pt.y;
    auto ch = convexHull(p);
    double bestR = 1e100; Point bestO;
    // 三點定圓
    for (int i=0; i

關鍵點

凸包點數通常遠小於 n (隨機分布下 O(log n))，三重循環可行
外接圓公式分母 D=0 表示三點共線，此時退化為兩點直徑情況
覆蓋判斷加 `1e-9` 容差，避免浮點誤差導致誤判
輸出保留兩位小數：`fixed << setprecision(2)`


最小覆蓋圓是計算幾何經典問題，「凸包降維 + 三點/兩點枚舉」是標準確定性算法，比模擬退火更穩健精確。