求二维点集中不能被所有其他点完全压制的点

概述

https://www.nowcoder.com/questionTerminal/f652bf7904bf4905804fa3bc347fdd2a

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

暴力法

后一半超时了。

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<array<int, 2>> points(n);
    for (int i = 0; i < n; i ++) {
        cin >> points[i][0] >> points[i][1];
    }
    auto points2 = points;
    sort(points.begin(), points.end(), [](const auto& a, const auto& b)->bool {
       return a[0] > b[0];
    });
    sort(points2.begin(), points2.end(), [](const auto& a, const auto& b)->bool {
       return a[1] > b[1];
    });
    for (int i = n - 1; i >= 0; i --) {
        auto c = points[i];
        bool ok = true;
        for (auto& p : points) {
            if (c[0] == p[0] && c[1] == p[1]) {
                break;
            }
            if (c[1] < p[1]) {
                ok = false;
                break;
            }
        }
        if (!ok) continue;
        for (auto& p : points2) {
            if (c[0] == p[0] && c[1] == p[1]) {
                break;
            }
            if (c[0] < p[0]) {
                ok = false;
                break;
            }
        }
        if (!ok) continue;
        cout << c[0] << " " << c[1] << endl;
    }
    return 0;
}

排序法

先按照 x 降序排序，对于 x 相同的情况，按照 y 降序排序。

时间复杂度 O(nlogn)。

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

struct Point {
    int x, y;
};

int main() {
    int n; cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i ++) {
        cin >> points[i].x >> points[i].y;
    }
    sort(points.begin(), points.end(), [](const auto& a, const auto& b)->bool {
       if (a.x == b.x) {
           return a.y > b.y;
       } else {
           return a.x > b.x;
       }
    });
    stack<Point*> s;
    int maxY = INT_MIN;
    for (auto& p : points) {
        if (p.y > maxY) {
            s.push(&p);
            maxY = p.y;
        }
    }
    while (!s.empty()) {
        cout << s.top()->x << " " << s.top()->y << endl;
        s.pop();
    }
    return 0;
}

还是超时了就离谱。

绝绝子，换 scanf 和 printf 就 okay（运行时间 218ms，原本的 cin 在第 8 题超时 1000ms），有这么离谱吗？属实是差别有点大了。

这搞得我不想用 cin & cout 了呀。

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

struct Point {
    int x, y;
};

int main() {
    int n; scanf("%d", &n);
    vector<Point> points(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d %d", &points[i].x, &points[i].y);
    }
    sort(points.begin(), points.end(), [](const auto& a, const auto& b)->bool {
        if (a.x == b.x) {
            return a.y > b.y;
        } else {
            return a.x > b.x;
        }
    });
    stack<Point*> s;
    int maxY = INT_MIN;
    for (auto& p : points) {
        if (p.y > maxY) {
            s.push(&p);
            maxY = p.y;
        }
    }
    while (!s.empty()) {
        printf("%d %d\n", s.top()->x, s.top()->y);
        s.pop();
    }
    return 0;
}

Links: 求二维点集中不能被所有其他点完全压制的点

未经允许，禁止转载，本文源站链接：https://iamazing.cn/