HDU 1086：線段相交計數——快速排斥與跨立實驗

問題描述

給定 N 條線段（N ≤ 100），求兩兩相交的對數。即使交點重疊也計為一次相交。輸入多組測試，N=0 結束。

線段相交判斷：兩大經典實驗

兩線段 AB、CD 相交的充要條件：

1. 快速排斥實驗：兩線段的外包矩形必須相交。即：

   max(A.x, B.x) ≥ min(C.x, D.x) &&
   max(C.x, D.x) ≥ min(A.x, B.x) &&
   max(A.y, B.y) ≥ min(C.y, D.y) &&
   max(C.y, D.y) ≥ min(A.y, B.y)

2. 跨立實驗：每條線段必須「跨立」在另一條線段所在直線的兩側（或端點在線上）。用叉積判斷：

   cross(A, C, D) * cross(B, C, D) ≤ 0 &&
   cross(C, A, B) * cross(D, A, B) ≤ 0

   其中 cross(P, Q, R) = (Q-P) × (R-Q) 表示向量 QP 到 QR 的叉積，正負表示左右關係。

兩條件同時滿足即相交（包含端點相交、重疊共線）。

代碼實現

struct point { double x, y; };
struct line { point s, e; };

double cross(point a, point b, point c) {
    double x1 = b.x - a.x, y1 = b.y - a.y;
    double x2 = c.x - b.x, y2 = c.y - b.y;
    return x1 * y2 - x2 * y1;
}

bool intersect(line a, line b) {
    if (max(a.s.x, a.e.x) < min(b.s.x, b.e.x) ||
        max(b.s.x, b.e.x) < min(a.s.x, a.e.x) ||
        max(a.s.y, a.e.y) < min(b.s.y, b.e.y) ||
        max(b.s.y, b.e.y) < min(a.s.y, a.e.y))
        return false; // 快速排斥失敗
    return cross(a.s, b.s, b.e) * cross(a.e, b.s, b.e) <= 0 &&
           cross(b.s, a.s, a.e) * cross(b.e, a.s, a.e) <= 0;
}

int main() {
    int n;
    while (scanf("%d", &n), n) {
        line seg[105];
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf%lf", &seg[i].s.x, &seg[i].s.y, &seg[i].e.x, &seg[i].e.y);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (intersect(seg[i], seg[j])) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

複雜度與優化

• N ≤ 100，O(N²) 兩兩檢查完全足夠（最多 4950 對）。
• 若 N 很大（如 10⁵），需用掃描線（Bentley-Ottmann）或空間分割優化至 O((N+K) log N)。

常見坑點

• 叉積公式簽名一致性：本代碼用 (b-a)×(c-b)，與標準 (b-a)×(c-a) 符號可能相反，但只關心正負乘積 ≤ 0，不影響邏輯。
• 共線重疊：跨立實驗中 ≤ 0 允許叉積為 0，即端點在線上或共線，符合題意「即使交點重疊也算在內」。
• 浮點精度：坐標為兩位小數，double 足夠精確；若涉及大數或高精度需引入 eps 比較。

總結

HDU 1086 是計算幾何入門必做題，核心考察「快速排斥 + 跨立實驗」判斷線段相交。代碼結構清晰，結構體封裝點/線段，叉積函數復用，邏輯直觀。掌握此模板可解決大多數平面線段相交計數問題。