最大点集

题目描述：

题目描述

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

如下图：实心点为满足条件的点的集合。

请实现代码找到集合P中的所有”最大“点的集合并输出。

输入描述:

第一行输入点集的个数N， 接下来N行，每行两个数字代表点的X轴和Y轴。1 ≤ n ≤ 500000

输出描述:

输出“最大的”点集合， 按照X轴从小到大的方式输出，每行两个数字分别代表点的X轴和Y轴。

示例1

输入

5
1 2
5 3
4 6
7 5
9 0

输出

4 6
7 5
9 0

思路:

先按照x升序和y升序排序，然后从后到前判断

代码:

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct num {
    int a,b;
};
bool cmp(struct num num1,struct num num2){
    if (num1.a > num2.a){
        return false;
    }else if (num1.a < num2.a){
        return true;
    }else{
        if (num1.b<num2.b){
            return true;
        }else{
            return false;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    struct num nums[n];
    struct num res[n];
    for (int i=0;i<n;i++){
        scanf("%d",&nums[i].a);
        scanf("%d",&nums[i].b);
    }
    sort(nums,nums+n,cmp);
    int k=1;
    int max = nums[n-1].b;
    res[0].a = nums[n-1].a;
    res[0].b = nums[n-1].b;
    for (int i=n-1;i>=0;i--){
        if(nums[i].b >max){
            max = nums[i].b;
            res[k].a = nums[i].a;
            res[k++].b = nums[i].b;
        }
    }
    for (int i=k-1;i>=0;i--){
        printf("%d %d\n",res[i].a,res[i].b);
    }
}

代码效率：

运行时间：173ms, 超过80.50%用C++提交的代码
占用内存：12684KB, 超过44.93%用C++提交的代码