HDU 1147 Pick-up Sticks：線段相交判定找出最頂層木棍

HDU 1147 Pick-up Sticks：線段相交判定找出最頂層木棍

題目大意

依序放下 n (≤100,000) 根木棍（線段）。一根木棍若未被後來木棍壓住（即無後續木棍與其相交），則可被取走。輸出所有可取走木棍的編號（1-based）。

解法

對每根木棍 i，檢查是否存在 j > i 與其相交。若無，則 i 可取走。需高效的線段相交判定。

線段相交判定（向量叉積法）

線段 AB 與 CD 相交 ⇔ C、D 在 AB 兩側（或共線）且 A、B 在 CD 兩側（或共線）。

double cross(Point a, Point b, Point c) { // AB x AC
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
bool onSegment(Point a, Point b, Point c) { // c 在線段 ab 上
    return min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x) &&
           min(a.y,b.y) <= c.y && c.y <= max(a.y,b.y);
}
bool segIntersect(Point a, Point b, Point c, Point d) {
    double d1 = cross(a, b, c);
    double d2 = cross(a, b, d);
    double d3 = cross(c, d, a);
    double d4 = cross(c, d, b);
    if (d1*d2 < 0 && d3*d4 < 0) return true; // 一般情況
    if (d1 == 0 && onSegment(a, b, c)) return true;
    if (d2 == 0 && onSegment(a, b, d)) return true;
    if (d3 == 0 && onSegment(c, d, a)) return true;
    if (d4 == 0 && onSegment(c, d, b)) return true;
    return false;
}

主邏輯

int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        Point p1[100005], p2[100005];
        for (int i = 0; i < n; ++i)
            scanf("%lf%lf%lf%lf", &p1[i].x, &p1[i].y, &p2[i].x, &p2[i].y);
        printf("Top sticks:");
        for (int i = 0; i < n; ++i) {
            bool ok = true;
            for (int j = i+1; j < n; ++j)
                if (segIntersect(p1[i], p2[i], p1[j], p2[j])) { ok = false; break; }
            if (ok) printf(" %d", i+1);
        }
        puts(".");
    }
    return 0;
}

複雜度與優化

• 暴力 O(n²) 在 n=10⁵ 會 TLE
• 實際 AC 代碼常用掃描線或空間分割優化，但題目測試數據較弱，暴力常能通過
• 正規解法：掃描線 + 平衡樹維護掃描線狀態，O(n log n)

樣例

輸入：
5
0 0 1 1
1 0 0 1
2 2 3 3
...
0

輸出：
Top sticks: 1 3 ...

此題是線段相交判定的直接應用，掌握叉積模板是關鍵。