我写了一个非常简(bao)单(li)的程序,竟然过了!

程序原理:先排好序,然后用类似筛法的思路,用每一个点去筛后面的点,如果发现后面的点中有非极大点直接删除.

代码如下:

#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;
}
vector<point>li;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		point p;
		cin>>p.x>>p.y;
		li.push_back(p);
	}
	sort(li.begin(),li.end(),cmp);
	for(int i=0;i<li.size();i++){
		for(int j=i+1;j<li.size();j++){
			if(li[i].x>=li[j].x&&li[i].y>=li[j].y){
				li.erase(li.begin()+j);
				j--;
			}
		}
	}
	for(int i=li.size()-1;i>=0;i--){
		cout<<"("<<li[i].x<<","<<li[i].y<<")";
		if(i!=0)cout<<",";
	}
}