POJ 1828 猴王問題：二維偏序掃描線 O(n log n) 解法

問題轉化

給定 n 個點 (x, y)。若存在另一點 (x', y') 滿足 x' ≥ x 且 y' ≥ y（且不全等），則該點被「支配」。求**不被任何其他點支配**的點的個數（即極大點 / 帕累托前沿 / 猴王）。

幾何直覺

支配關係對應矩形區域：點 A 支配點 B ⇔ B 落在以 A 為右上角、原點為左下角的矩形內。所有極大點連成一條從右上到左下的「階梯線」。

掃描線算法

1. 排序：按 x 降序，x 相同按 y 降序。
2. 掃描：維護當前最大 y 值 maxY（初始 -∞）。
3. 判斷：遍歷排序後的點，若 y > maxY，則該點不被支配，計數++，更新 maxY = y；否則被支配，跳過。
4. 同 x 處理：同 x 時 y 最大者優先被訪問，後續同 x 且 y 較小者必被支配（因 x 相同、y 更小），邏輯自動覆蓋。

複雜度

• 排序 O(n log n)
• 掃描 O(n)
• 總 O(n log n)，空間 O(n)

代碼框架

#include <bits/stdc++.h>
using namespace std;

struct Point { int x, y; };

bool cmp(Point a, Point b) {
    if (a.x != b.x) return a.x > b.x;
    return a.y > b.y;
}

int main() {
    int n;
    while (cin >> n) {
        vector<Point> p(n);
        for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
        sort(p.begin(), p.end(), cmp);
        int ans = 0, maxY = -1;
        for (auto &pt : p) {
            if (pt.y > maxY) { ++ans; maxY = pt.y; }
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵細節

• 坐標範圍未給出，int 足夠；若超大用 long long。
• 輸入可能多測試用例，直到 EOF。
• 「不存在其他點 x'≥x 且 y'≥y」等價於「在按 x 降序掃描時，y 严格大於之前所有點的最大 y」。

延伸應用

• 二維偏序問題：求極大點集、支配計數、CDQ 分治求三維偏序。
• 天際線問題、投資組合優化、多目標優化帕累托前沿。