寻找平面上的极大点

题目描述

平面上有 $n$ 个互不相同的整点 $(x_i,y_i)$ 。若 $x \geqslant a$ 且 $y \geqslant b$ ，则称 $(x,y)$ 支配 $(a,b)$ 。要求输出所有不被其它点支配的极大点，按 $x$ 坐标从小到大。 $n \leqslant 100$ ，坐标非负。

样例： $(1,2),(2,2),(3,1),(2,3),(1,4)$ 的极大点为 $(1,4),(2,3),(3,1)$ 。

思路

按 $x$ 降序、 $y$ 降序排序后扫描：已扫过的点都满足 $x' \geqslant x$ ，所以当前点是极大点当且仅当 $y$ 大于已扫过的最大 $y$ 。扫描得到的点 $x$ 递减，反转即为答案顺序。注意支配允许取等，因此判断要用严格大于。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:42
# update_at: 2026-09-30 00:42

import sys


def maximal_points(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """按 x 从小到大返回所有极大点（没有任何其它点同时不小于它的 x 与 y）。

    按 x 降序、y 降序扫描：已扫过的点 x 都不小于当前点，其中最大的 y 记为 max_y。
    当前点被支配 <=> 存在已扫过的点 y' >= y <=> y <= max_y，故 y > max_y 即为极大点。
    """
    found: list[tuple[int, int]] = []
    max_y = -1  # 坐标非负，-1 是比任何真实 y 都小的哨兵
    for x, y in sorted(points, reverse=True):  # 元组排序：x 降序，x 相同则 y 降序
        if y > max_y:
            found.append((x, y))
            max_y = y
    return found[::-1]  # 扫描得到 x 递减，反转即为题目要求的 x 递增


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    points = [(next(data), next(data)) for _ in range(n)]

    print(','.join(f'({x},{y})' for x, y in maximal_points(points)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:04
 * update_at: 2026-10-05 06:04
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

struct Point {
    ll x;
    ll y;
} p[MAXN]; // 输入点集

Point ans[MAXN]; // 极大点结果，按 x 递增存放
int ans_cnt;     // 极大点个数

// 按 x 降序排序，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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }

    sort(p + 1, p + n + 1, cmp);

    ll max_y = -1; // 坐标非负，-1 作为比所有真实 y 都小的哨兵
    for (int i = 1; i <= n; i++) {
        // 已扫过的点 x 都不小于当前点，只需判断 y 是否大于已扫最大 y
        if (p[i].y > max_y) {
            ans[++ans_cnt] = p[i];
            max_y = p[i].y;
        }
    }

    // 扫描结果 x 递减，反转后得到题目要求的 x 递增顺序
    for (int i = ans_cnt; i >= 1; i--) {
        cout << '(' << ans[i].x << ',' << ans[i].y << ')';
        if (i > 1) cout << ',';
    }
    cout << '\n';

    return 0;
}

寻找平面上的极大点

目录

题目描述

思路

参考代码