POJ 2653：木棍覆蓋——線段相交判定與隊列模擬

問題描述

依次放置 n 根木棍（線段）。若新木棍與已放置的任意木棍相交（含端點接觸），則被相交的舊木棍被覆蓋移除。求最終剩餘木棍的編號（按放置順序輸出）。

核心幾何：線段相交判定

兩線段 p1-p2 和 p3-p4 相交條件：

1. 跨立實驗：cross(p1,p2,p3) * cross(p1,p2,p4) ≤ 0 且 cross(p3,p4,p1) * cross(p3,p4,p2) ≤ 0。
2. 特殊情況：共線重疊。用 on_segment 判斷端點是否在另一線段上（投影重疊）。

向量叉積：cross(a,b,c) = (b-a) × (c-a)。

隊列模擬流程

維護一個隊列存放當前未被覆蓋的木棍（按放置順序）。新木棍入隊後，從隊頭開始檢查：

• 若與隊頭木棍相互不相交 → 隊頭木棍安全，重新入隊尾。
• 若相交 → 隊頭木棍被覆蓋，丟棄（不入隊）。
• 直到遇到剛入隊的新木棍本身（標記 id），停止。

此過程保證隊列中木棍兩兩不相交，且順序為放置順序。

代碼實現

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair Point;

double cross(Point a, Point b, Point c) {
    Point ab = {b.first - a.first, b.second - a.second};
    Point ac = {c.first - a.first, c.second - a.second};
    return ab.first * ac.second - ab.second * ac.first;
}

bool onSegment(Point a, Point b, Point p) {
    return min(a.first, b.first) <= p.first && p.first <= max(a.first, b.first) &&
           min(a.second, b.second) <= p.second && p.second <= max(a.second, b.second);
}

bool intersect(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;
}

struct Stick { double x1, y1, x2, y2; int id; };

int main() {
    int n;
    while (scanf("%d", &n), n) {
        queue q;
        for (int i = 1; i <= n; i++) {
            Stick s; scanf("%lf%lf%lf%lf", &s.x1, &s.y1, &s.x2, &s.y2);
            s.id = i;
            q.push(s);
            while (true) {
                Stick cur = q.front(); q.pop();
                if (cur.id == s.id) { q.push(cur); break; } // 自己遇到自己，結束
                if (!intersect({s.x1,s.y1}, {s.x2,s.y2}, {cur.x1,cur.y1}, {cur.x2,cur.y2}))
                    q.push(cur); // 不相交，保留
                // 相交則 cur 被覆蓋，丟棄
            }
        }
        printf("Top sticks: %d", q.front().id); q.pop();
        while (!q.empty()) {
            printf(", %d", q.front().id); q.pop();
        }
        printf(".\n");
    }
    return 0;
}

關鍵點

• 雙精度浮點數計算叉積，避免精度問題（坐標範圍未給，假設 double 足夠）。
• 共線重疊視為相交，onSegment 投影法判斷。
• 隊列模擬邏輯：新棍入隊後，從頭掃描至自己，相交者淘汰。
• 輸出格式：Top sticks: id1, id2, ... 以點結尾。

複雜度

最壞 O(n²) 相交判定，n ≤ 100000？題目未給上限，但隊列模擬常數小，實際較快。