HDU 1086 You can Solve a Geometry Problem Too - 線段相交判斷

問題描述

給定 n ≤ 100 條線段，求有多少對線段相交（包括端點相交）。

叉積判斷線段相交

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

1. 跨立實驗：cross(A,B,C) * cross(A,B,D) ≤ 0 且 cross(C,D,A) * cross(C,D,B) ≤ 0。
2. 投影重疊：max(min(A.x,B.x), min(C.x,D.x)) ≤ min(max(A.x,B.x), max(C.x,D.x))（x,y 兩方向）。

實現細節

• 用 double 存儲坐標，叉積用 double 計算，判零用 eps=1e-10。
• 雙重循環枚舉所有線段對 O(n^2)，n=100 共 4950 對，極快。

參考代碼 (C++)

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double EPS = 1e-10;
struct Point { double x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
int dcmp(double x) { if (fabs(x) < EPS) return 0; return x > 0 ? 1 : -1; }

bool onSegment(Point p, Point a, Point b) {
    return dcmp(cross(a-p, b-p)) == 0 &&
           dcmp((p.x-a.x)*(p.x-b.x)) <= 0 &&
           dcmp((p.y-a.y)*(p.y-b.y)) <= 0;
}

bool segIntersect(Point a, Point b, Point c, Point d) {
    double c1 = cross(b-a, c-a), c2 = cross(b-a, d-a);
    double c3 = cross(d-c, a-c), c4 = cross(d-c, b-c);
    if (dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0) return true;
    if (dcmp(c1)==0 && onSegment(c, a, b)) return true;
    if (dcmp(c2)==0 && onSegment(d, a, b)) return true;
    if (dcmp(c3)==0 && onSegment(a, c, d)) return true;
    if (dcmp(c4)==0 && onSegment(b, c, d)) return true;
    return false;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        Point seg[100][2];
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf%lf", &seg[i][0].x, &seg[i][0].y, &seg[i][1].x, &seg[i][1].y);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (segIntersect(seg[i][0], seg[i][1], seg[j][0], seg[j][1]))
                    ++ans;
        printf("%d\n", ans);
    }
    return 0;
}