BZOJ 1007 [HNOI2008] 水平可見直線：單調棧幾何解法完整解析

問題描述

給定 N 條直線 y = k_i x + b_i (N ≤ 50000)，從左側（x → -∞）觀察，輸出可見直線的編號（從小到大）。若多條直線在同一位置，只保留截距最大者。

幾何直觀與轉化

從 x → -∞ 看，斜率較大（較不陡峭）的直線在左側較高。將直線按斜率 k 降序排序（即從最陡峭負斜率到最平緩正斜率）。

維護一個「下凸包」：新加入的直線若能「蓋住」棧頂直線，則彈出棧頂。

判斷條件推導

設棧中已有直線 L1（綠）、L2（藍），新加入 L3（紅）。
L1 與 L3 交點 x 座標：x13 = (b3 - b1) / (k1 - k3)
L2 與 L3 交點 x 座標：x23 = (b3 - b2) / (k2 - k3)

若 x13 ≤ x23，說明 L3 在 L1 右側就超過 L2，L2 永遠被遮擋 → 彈出 L2。
否則 L2 保留。

預處理：同斜率去重

按 k 降序排序後，同 k 只保留 b 最大者（其餘永遠被遮擋）。

算法流程

1. 讀入直線，附帶原始編號
2. 按 k 降序排序，同 k 保留最大 b
3. 初始化棧，放入第一條直線
4. 對後續每條直線：
   　while 棧大小 ≥ 2 且 x(stack[top-1], cur) ≤ x(stack[top], cur) + eps：
   　　棧彈頂
   　棧壓入當前直線
5. 棧中剩餘直線即為可見直線，按原始編號排序輸出

關鍵代碼

struct Line { int k, b, id; } a[N], tmp[N];

double crossX(Line u, Line v) {  // 交點 x 座標
    return (double)(v.b - u.b) / (u.k - v.k);
}

bool cmpK(Line u, Line v) {  // k 降序，同 k 取大 b
    return u.k > v.k || (u.k == v.k && u.b > v.b);
}

bool cmpId(int u, int v) { return a[u].id < a[v].id; }

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].k, &a[i].b), a[i].id = i;
    
    sort(a+1, a+n+1, cmpK);
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 1 && a[i].k == a[i-1].k) continue;  // 同斜率只保留第一個（b 最大）
        tmp[++m] = a[i];
    }
    
    int stk[N], top = 0;
    stk[++top] = 1;
    for (int i = 2; i <= m; i++) {
        while (top >= 2) {
            double x1 = crossX(tmp[stk[top-1]], tmp[i]);
            double x2 = crossX(tmp[stk[top]], tmp[i]);
            if (x1 <= x2 + 1e-9) top--;
            else break;
        }
        stk[++top] = i;
    }
    
    sort(stk+1, stk+top+1, cmpId);
    for (int i = 1; i <= top; i++) printf("%d ", tmp[stk[i]].id);
    return 0;
}

複雜度分析

• 排序：O(N log N)
• 單調棧：每條直線進棧出棧各一次 → O(N)
• 總體：O(N log N) 時間，O(N) 空間

精度處理

• 交點計算用 double，比較時加 1e-9 容差
• 輸入係數 ≤ 40000，double 精度足夠

總結

本題將「可見直線」轉化為「下凸包維護」，利用斜率單調性實現 O(N log N) 單調棧解法。關鍵在於交點比較判斷遮擋關係，以及同斜率預處理。