HDU 3694 四邊形費馬點：凸包 + 對角線交點幾何解法

問題重述

給定平面四點，求一點 P 使 ∑|P-Pi| 最小。此即四邊形的費馬點（幾何中位數）。

幾何性質

• 凸四邊形：費馬點為對角線交點。
• 凹四邊形：費馬點為凹頂點（內角 > 180° 的頂點）。
• 退化情況（三點共線、重合點）需單獨處理。

算法流程

1. 讀入四點 p[0..3]。
2. 用 Graham Scan 或 Andrew 算法求凸包，得到凸包頂點序列 ch 及大小 len。
3. 若 len == 4（凸四邊形）：計算對角線 p0-p2 與 p1-p3 交點，作為候選點。
4. 無論凸凹，四個原始頂點均為候選點（凹情況下最優解即為凹頂點）。
5. 對所有候選點計算距離和，取最小值。

核心幾何工具

struct Pt { double x, y; };
double cross(Pt a, Pt b, Pt o) { // (a-o) × (b-o)
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double dist(Pt a, Pt b) {
    return hypot(a.x-b.x, a.y-b.y);
}
Pt lineInter(Pt a1, Pt a2, Pt b1, Pt b2) {
    // a1 + t*(a2-a1) = b1 + s*(b2-b1)
    double t = cross(b1, b2, a1) / cross(a2, b2, a1);
    return {a1.x + (a2.x-a1.x)*t, a1.y + (a2.y-a1.y)*t};
}

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
struct Pt { double x, y; };
double cross(Pt a, Pt b, Pt o) { return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x); }
double dist(Pt a, Pt b) { return hypot(a.x-b.x, a.y-b.y); }
Pt inter(Pt a, Pt b, Pt c, Pt d) {
    double t = cross(c, d, a) / cross(b, d, a);
    return {a.x + (b.x-a.x)*t, a.y + (b.y-a.y)*t};
}
vector<Pt> convexHull(vector<Pt> p) {
    sort(p.begin(), p.end(), [](Pt a, Pt b){
        return a.y=2 && cross(pt, ch.back(), ch[ch.size()-2]) >= 0)
            ch.pop_back();
        ch.push_back(pt);
    }
    int k = ch.size();
    for (int i = p.size()-2; i >= 0; --i) {
        while (ch.size() > k && cross(p[i], ch.back(), ch[ch.size()-2]) >= 0)
            ch.pop_back();
        ch.push_back(p[i]);
    }
    if (!ch.empty()) ch.pop_back();
    return ch;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Pt p[4];
    while (cin >> p[0].x >> p[0].y) {
        bool end = (p[0].x==-1 && p[0].y==-1);
        for (int i=1;i<4;++i) { cin>>p[i].x>>p[i].y; end &= (p[i].x==-1 && p[i].y==-1); }
        if (end) break;
        double best = 1e100;
        // 候選：四個頂點
        for (int i=0;i<4;++i) {
            double sum = 0;
            for (int j=0;j<4;++j) sum += dist(p[i], p[j]);
            best = min(best, sum);
        }
        // 凸包
        vector<Pt> v(p, p+4);
        auto ch = convexHull(v);
        if (ch.size() == 4) { // 凸四邊形
            Pt center = inter(p[0], p[2], p[1], p[3]);
            double sum = 0;
            for (int i=0;i<4;++i) sum += dist(center, p[i]);
            best = min(best, sum);
        }
        cout << fixed << setprecision(4) << best << '\n';
    }
    return 0;
}

注意事項

• Graham Scan 需處理共線點：`cross >= 0` 保留最遠點，`cross > 0` 剔除共線點。題目中共線情況退化為線段，頂點遍歷已覆蓋最優解。
• 對角線交點公式分母為 0 時（平行/共線）不會在凸四邊形出現。
• 輸出精度 %.4f。