BZOJ 1007 HNOI2008 水平可見直線 - 計算幾何 + 單調棧維護上凸包

題目大意

給定平面直角坐標系內若干直線 y = kx + b。從 y = +∞ 向下看，哪些直線的某段是可見的 (未被其他直線遮擋)？輸出可見直線的原始編號 (1-based)。

幾何轉化：上凸包 / 半平面交特例

從 +∞ 向下看，可見直線即為上包絡線 (Upper Envelope) 構成段所屬直線。等價於求直線集合的上凸包 (按斜率排序後維護)。

單調棧算法 (類 Andrew 凸包)

1. 按斜率 k 升序排序，k 相同時保留 b 最大者 (其餘被完全遮擋)。
2. 維護棧，棧中直線斜率嚴格遞增，交點横坐標嚴格遞增。
3. 加入新直線 L 時：

while (棧大小 ≥ 2 && L 與棧頂交點 x ≤ 棧頂與次棧頂交點 x) 棧彈頂;
棧推入 L;

最終棧中直線即為可見直線 (按斜率序)。

關鍵幾何函數

Point intersection(Line l1, Line l2) { // l1.k != l2.k
    double x = (l2.b - l1.b) / (l1.k - l2.k);
    return {x, l1.k * x + l1.b};
}
bool under(Line l, Point p) { // 直線 l 在點 p 處是否在 p 上方或重合 (遮擋)
    return l.k * p.x + l.b >= p.y - EPS;
}

去重邏輯

排序後，k 相同只保留 b 最大的一條 (其餘不可見)。代碼中先排序，再遍歷跳過 k 相同者 (僅保留第一個，即 b 最大)。

完整代碼

#include 
using namespace std;
const int MAXN = 50010;
const double EPS = 1e-5;

struct Line { double k, b; int id; };
Line lines[MAXN], *stk[MAXN];
Point its[MAXN];
bool vis[MAXN];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        scanf("%lf%lf", &lines[i].k, &lines[i].b);
        lines[i].id = i;
    }
    sort(lines+1, lines+n+1, [](Line a, Line b) {
        if (fabs(a.k - b.k) < EPS) return a.b > b.b;
        return a.k < b.k;
    });
    // 去重：k 相同只保留第一個 (b 最大)
    int m = 0;
    for (int i = 1; i <= n; ++i)
        if (i == 1 || fabs(lines[i].k - lines[i-1].k) > EPS)
            lines[++m] = lines[i];
    
    int top = 0;
    stk[++top] = &lines[1];
    stk[++top] = &lines[2];
    its[1] = intersection(lines[1], lines[2]);
    
    for (int i = 3; i <= m; ++i) {
        while (top > 1 && under(*stk[top], its[top-1])) --top;
        stk[++top] = &lines[i];
        its[top-1] = intersection(*stk[top], *stk[top-1]);
    }
    
    for (int i = 1; i <= top; ++i) vis[stk[i]->id] = true;
    for (int i = 1; i <= n; ++i) if (vis[i]) printf("%d ", i);
    return 0;
}

複雜度

• 排序：O(n log n)。
• 棧處理：O(n)。
• 總計：O(n log n)，n ≤ 50000 極快。

關鍵細節

• EPS = 1e-5 雙精度比較。
• 交點横坐標遞增性保證棧操作正確性。
• 輸出原始編號，需記錄 id。