NYOJ 1099 Lan Xiang's Square：四點判正方形的幾何鑑別法

題目描述

給定平面上四個點（座標為整數，範圍 ±10⁸），判斷它們能否構成一個正方形。能則輸出 "Yes"，否則 "No"。多測試案例，T ≤ 10⁵。

幾何判別條件

四邊形為正方形的充要條件（任一）：

1. 四邊等長 + 一個角為直角（最直觀）。
2. 四邊等長 + 兩條對角線等長（等價於菱形+矩形）。
3. 六條兩兩距離中，四條最小相等（邊長），兩條最大相等（對角線），且對角線² = 2 × 邊長²（僅用距離平方，避免開根號）。

推薦做法：距離平方排序法

1. 計算六條兩兩距離的平方 d[6]。
2. 排序 d。
3. 判斷：
   d[0] > 0 && d[0]==d[1] && d[1]==d[2] && d[2]==d[3] && // 四邊相等
d[4]==d[5] && // 對角線相等
d[4] == 2 * d[0] // 畢達哥拉斯關係

此法無需判斷點序、無浮點誤差、邏輯極簡。

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Pt { ll x, y; };

ll dist2(const Pt& a, const Pt& b) {
    ll dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        Pt p[4];
        for (int i = 0; i < 4; ++i) cin >> p[i].x >> p[i].y;
        ll d[6]; int cnt = 0;
        for (int i = 0; i < 4; ++i)
            for (int j = i+1; j < 4; ++j)
                d[cnt++] = dist2(p[i], p[j]);
        sort(d, d+6);
        bool ok = (d[0] > 0) &&
                  (d[0] == d[1] && d[1] == d[2] && d[2] == d[3]) &&
                  (d[4] == d[5]) &&
                  (d[4] == 2 * d[0]);
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

原作者 WA 經驗教訓

• 浮點誤差：用 sqrt 計算邊長再比較，導致精度丟失 WA。永遠用距離平方整數運算。
• 點序假設錯誤：嘗試用幾何中心排序四點，再判斷邊與對角線，邏輯複雜且易漏情況（如點重合、共線）。
• 距離平方排序法 完全規避上述問題，且 O(1) 時間，極適合大數據量。

複雜度

• 每案例：6 次距離計算 + 排序 6 個數 = O(1)。
• 總時間 O(T)，T ≤ 10⁵ 極易通過。

總結

判斷四點是否構成正方形，**距離平方排序法** 是最簡潔、最穩健、最不易出錯的做法。核心洞見：正方形的 6 條兩兩距離中，必有 4 條相等的邊長、2 條相等的對角線，且滿足 對角線² = 2 × 邊長²。拒絕浮點，拒絕複雜點序邏輯，一行判斷搞定一切。