UVA 11106 Rectilinear Polygon：直角多邊形周長計算與有效性判斷

給定 N 個點（N ≤ 10^5），判斷能否將它們連成一個所有內角為 90°/270° 的簡單多邊形（即邊平行坐標軸，無自相交，無三點共線），若能則輸出周長，否則輸出 -1。

幾何性質與必要條件

1. N 必須為偶數：每條邊平行 x 或 y 軸，水平邊與垂直邊數量相等，總邊數為偶數。
2. 同 x 坐標點數為偶數，按 y 排序後兩兩配對形成垂直邊；同 y 坐標同理形成水平邊。
3. 所有點連通：邊構成的圖必須連通（單一多邊形）。
4. 無邊相交：水平邊與垂直邊除端點外不相交。

算法流程

1. 構建候選邊

• 按 x 分組，組內按 y 排序，相鄰兩點配對 → 垂直邊 (x, y1, y2)，累加長度 y2-y1，並查集合併兩端點。
• 按 y 分組，組內按 x 排序，相鄰兩點配對 → 水平邊 (y, x1, x2)，累加長度，並查集合併。
• 若任一組點數為奇數 → 直接返回 -1。

2. 檢查連通性

• 構建完所有邊後，檢查所有點是否屬於同一並查集集合。若不連通 → -1。

3. 檢查邊相交（掃描線 + 優先隊列/鏈表優化）

• 垂直邊按 x 排序；水平邊按 y 掃描。
• 掃描到水平邊 (y, x1, x2) 時：
  • 將所有 x < y 的垂直邊按 y1 入優先隊列（小頂堆按 y2）。
  • 移除隊列中 y2 <= y 的垂直邊（已掃過）。
  • 遍歷隊列中剩餘垂直邊，若存在 x1 < x < x2 → 相交 → -1。
• 為優化遍歷刪除，代碼使用鏈表實現優先隊列，支持 O(1) 刪除指定節點。

關鍵代碼邏輯

// 垂直邊結構
struct Seg { int x, y1, y2, t; }; // t: 0=垂直, 1=水平

// 掃描水平邊
sort(vert, vert+m, cmpX); // 按 x
sort(horiz, horiz+n, cmpY); // 按 y

priority_queue pq; // 存活垂直邊，按 y2
ListNode *head = new ListNode(0); // 鏈表頭，同步 pq 內容

for (each horiz edge h) {
    // 入隊：vert[v].x < h.y
    while (v < m && vert[v].x < h.y) {
        pq.push(vert[v]);
        insertList(head, vert[v].t); // t 為垂直邊 x 坐標
        v++;
    }
    // 出隊：pq.top().y2 <= h.y
    while (!pq.empty() && pq.top().y2 <= h.y) {
        deleteList(head, pq.top().t);
        pq.pop();
    }
    // 檢查相交：遍歷鏈表，若節點 x 在 (h.x1, h.x2) 內 → 相交
    for (node = head->next; node; node = node->next)
        if (node->t > h.x1 && node->t < h.x2) return -1;
}
// 最後檢查並查集連通數
if (components > 1) return -1;
return total_perimeter;

複雜度

• 排序：O(N log N)
• 掃描線：每條邊入隊/出隊一次，鏈表遍歷總長度 O(M)，整體 O(N log N)。
• 空間：O(N)

總結

本題綜合考察幾何性質推導、並查集連通性、掃描線相交檢測、優先隊列與鏈表協同優化。關鍵在於識別「同坐標兩兩配對」的必然性，並用掃描線高效檢測軸平行線段相交。代碼中鏈表優化優先隊列刪除是工程實現的亮點。