HDU 1558 Segment Set：幾何判斷 + 並查集離線處理

題目大意

平面上動態添加線段，支援兩種操作：
A x1 y1 x2 y2：添加線段。
Q k：查詢第 k 條線段所在的連通塊大小（線段相交視為連通）。
多測試案例，輸出每個 Q 的答案。

核心觀察

• 線段相交判斷：向量叉積法。兩線段 (x1,y1)-(x2,y2) 和 (x3,y3)-(x4,y4) 相交 ⇔
  cross(p2-p1, p3-p1) * cross(p2-p1, p4-p1) ≤ 0 且
  cross(p4-p3, p1-p3) * cross(p4-p3, p2-p3) ≤ 0，並處理共線重疊情況。
• 操作離線：所有添加操作先存儲，查詢時需知道當前已添加的線段關係。因為只有添加無刪除，可用並查集動態維護連通塊。
• 每次添加新線段時，與所有已有線段檢查相交，相交則合併集合。

算法流程

1. 讀取測試案例數 T。
2. 每案例：
   a. 初始化並查集 fa[]、大小 sz[]。
   b. 讀取 m 操作。
   c. 對每個操作：
     • A：存儲線段端點，編號 tot++。遍歷所有已有線段 j < tot，若相交則 union(tot, j)。
     • Q k：輸出 sz[find(k)]。
   d. 案例間輸出空行。

關鍵代碼片段

struct Seg { double x1, y1, x2, y2; } seg[2024];
int fa[1024], sz[1024], tot;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) { fa[a] = b; sz[b] += sz[a]; }
}

// 叉積
double cross(double x1, double y1, double x2, double y2) {
    return x1 * y2 - x2 * y1;
}

// 線段相交判斷（含端點、共線重疊）
bool intersect(int i, int j) {
    double x1 = seg[i].x1, y1 = seg[i].y1, x2 = seg[i].x2, y2 = seg[i].y2;
    double x3 = seg[j].x1, y3 = seg[j].y1, x4 = seg[j].x2, y4 = seg[j].y2;
    double c1 = cross(x2-x1, y2-y1, x3-x1, y3-y1);
    double c2 = cross(x2-x1, y2-y1, x4-x1, y4-y1);
    double c3 = cross(x4-x3, y4-y3, x1-x3, y1-y3);
    double c4 = cross(x4-x3, y4-y3, x2-x3, y2-y3);
    if (c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) { // 共線
        // 投影到 x 或 y 軸檢查重疊
        if (max(x1,x2) < min(x3,x4) || max(x3,x4) < min(x1,x2)) return false;
        if (max(y1,y2) < min(y3,y4) || max(y3,y4) < min(y1,y2)) return false;
        return true;
    }
    return c1 * c2 <= 0 && c3 * c4 <= 0;
}

複雜度分析

• 最多 1000 條線段（m ≤ 1000）。
• 每次添加檢查 O(tot) 條線段，總相交檢查 O(m²) = 10⁶，足夠快。
• 並查集操作近似 O(1)。
• 總時間 O(m²) 每案例，空間 O(m)。

常見坑點

• 雙精度比較：叉積結果為 0 時需用 fabs(v) < eps，但題目座標為整數，直接用 == 0 安全。
• 共線重疊單獨處理，否則叉積法會漏判。
• 案例間輸出空行，最後一案例不輸出。

總結

HDU 1558 是「幾何判斷 + 並查集離線動態連通性」的經典結合。關鍵在於正確實現線段相交判斷（含共線情況），並利用並查集高效維護連通塊大小。代碼簡潔，邏輯清晰，是幾何+數據結構入門好題。