CodeForces 23D Tetragon - 給定凸四邊形三邊中點求頂點

題目大意

給定平面上 3 個點，它們是某凸四邊形 3 條等長邊的中點。求該四邊形 4 個頂點（按順序輸出），或判斷不存在。

幾何構造原理

關鍵觀察

設三中點為 M1, M2, M3，對應邊長相等。
將 M2 關於 M1 對稱得 M2'。
則 M1, M2, M2' 共線，且 M1M2 = M1M2'。
四邊形其中一頂點 O 到 M1, M2, M3 距離相等 → O 是 M1, M2, M2' 三點的外心（圓心）。

構造步驟

1. 枚舉 3 個中點中哪個是「中間」的（共 3 種）
2. 設該中點為 A，另外兩個為 B, C
3. B' = B 關於 A 對稱：B' = 2A - B
4. 求 A, B', C 三角形外心 O（即頂點 1）
5. 其他頂點由對稱得出：
   • P2 = 2A - O
   • P3 = 2B - P2
   • P4 = 2C - O
6. 驗證凸性：對角線 P1P3 與 P2P4 相交

外心計算

三角形 A(x1,y1), B(x2,y2), C(x3,y3) 外心：

a1 = x2-x1, b1 = y2-y1, c1 = (a1²+b1²)/2
a2 = x3-x1, b2 = y3-y1, c2 = (a2²+b2²)/2
d = a1*b2 - a2*b1
Ox = x1 + (c1*b2 - c2*b1)/d
Oy = y1 + (a1*c2 - a2*c1)/d

完整程式碼核心

struct Pt { double x, y; };

Pt operator-(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }
Pt operator+(Pt a, Pt b) { return {a.x+b.x, a.y+b.y}; }
Pt operator*(Pt a, double k) { return {a.x*k, a.y*k}; }

Pt circumcenter(Pt a, Pt b, Pt c) { /* 上述公式 */ }
Pt reflect(Pt p, Pt center) { return center*2 - p; }

bool check(Pt a, Pt b, Pt c) {
    Pt bb = reflect(b, a);
    if (dist(a,b) == dist(a,c)) return false; // 退化
    Pt o = circumcenter(a, bb, c);
    Pt p1 = o, p2 = reflect(o, a), p3 = reflect(p2, b), p4 = reflect(o, c);
    return segments_intersect(p1, p3, p2, p4); // 對角線相交 = 凸
}

int main() {
    Pt m[3];
    while (read 3 points) {
        bool ok = check(m[0],m[1],m[2]) || check(m[1],m[0],m[2]) || check(m[2],m[1],m[0]);
        if (ok) output 4 vertices;
        else print "NO";
    }
}

複雜度

• 常數次幾何運算，O(1)
• 精度控制用 eps = 1e-8