POJ 1788 圍欄長度計算：坐標排序與配對累加算法詳解

問題描述

給定 N 個樁的坐標 (x, y)，圍欄只沿東西或南北方向，且只在轉彎處有樁。求圍欄總長度。即：給定一組點，它們構成若干條水平/垂直線段，線段端點在給定點集中，且每個點是恰好兩條線段的端點（度為 2），形成封閉多邊形（可能多個）。計算所有線段長度之和。

核心觀察

• 水平線段：端點 y 相同，x 不同。每條線段對應一對 (x1, y), (x2, y)。
• 垂直線段：端點 x 相同，y 不同。每條線段對應一對 (x, y1), (x, y2)。
• 每個 x 坐標下的點，按 y 排序後，兩兩配對 (第1、2點；第3、4點...)，每對構成一條垂直線段。
• 每個 y 坐標下的點，按 x 排序後，兩兩配對，構成水平線段。
• 題目保證每組點數為偶數，配對完美。

算法流程

1. 讀入所有點。
2. 按 x 分組：使用 map<int, vector<int>> x2ys，收集同 x 下的所有 y。
3. 對每個 x 的 y 列表排序，累加 y[2i+1] - y[2i] 到答案。
4. 按 y 分組：map<int, vector<int>> y2xs，收集同 y 下的所有 x。
5. 對每個 y 的 x 列表排序，累加 x[2i+1] - x[2i] 到答案。
6. 輸出總和。

時間複雜度

• 分組：O(N)
• 排序：每組排序，總計 O(N log N) (所有點參與一次排序)
• 累加：O(N)
• 總體：O(N log N)，空間 O(N)

代碼實現 (C++)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        map> x2ys, y2xs;
        for (int i=0; i> x >> y;
            x2ys[x].push_back(y);
            y2xs[y].push_back(x);
        }
        
        long long ans = 0;
        for (auto &kv : x2ys) {
            auto &ys = kv.second;
            sort(ys.begin(), ys.end());
            for (size_t i=0; i+1