POJ 3990 Fermat Point in Quadrangle：凸包判斷 + 費馬點性質

題目大意

給四邊形四個頂點（順序隨機），求其費馬點（使到四頂點距離和最小的點）的最小距離和。輸出保留 4 位小數。

核心幾何性質

• **凸四邊形**：費馬點 = 兩條對角線交點。距離和 = 對角線長度之和。
• **凹四邊形**：費馬點 = 凹頂點（內角 > 180° 的頂點）。距離和 = 該頂點到其他三頂點距離和。

算法流程

1. 讀入 4 點。
2. 求**凸包**（Graham Scan 或 Andrew 算法），得到凸包頂點序列。
3. 若凸包大小 = 4 → 凸四邊形，計算對角線和。
   對角線為凸包中對向的兩對點（如 0-2, 1-3）。
4. 若凸包大小 = 3 → 凹四邊形，內點即為凹點。遍歷 4 點，計算各點到其他三點距離和，取最小值。

代碼關鍵片段

struct Point { double x, y; };
double cross(Point a, Point b, Point c) { // (b-a)×(c-a)
    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); }

int graham(Point p[], int n, Point ch[]) {
    sort(p, p+n, [](Point a, Point b){ return a.y=2 && cross(ch[top-2], ch[top-1], p[i]) <= 0) --top;
        ch[top++] = p[i];
    }
    int lower = top;
    for (int i=n-2;i>=0;--i) {
        while (top>lower && cross(ch[top-2], ch[top-1], p[i]) <= 0) --top;
        ch[top++] = p[i];
    }
    return top-1; // 凸包點數
}

複雜度

• 凸包 O(4 log 4) = O(1)。
• 距離計算 O(1)。

總結

POJ 3990 利用四邊形費馬點的幾何性質，配合凸包判斷凸/凹，極簡解決。關鍵洞見：凸四邊形費馬點為對角線交點，凹四邊形為凹點。無需模擬退火等啟發式算法。