评论详情-牛客网

1.先对所有点集按y的降序排列，存放到vector变量中

x1, x2, ... , xn

y1>y2>...>yn

2.判断(xi,yi)（其中i=1,...,n）是否满足题目要求的“最大的”点

满足要求为：xi>xj，j=1,...,i-1;

因为点集已经按照y的降序进行排列，判断(xi,yi)时，只有y值比yi大的点（即该点在(xi,yi)的左上方或右上方）可能导致(xi,yi)不是“最大的点”，接着排除右上方的可能性，即满足上述要求

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int,int> point1, pair<int, int> point2)
{
	if(point1.second > point2.second)
		return true;
	else
		return false;
}

int main(int argc, char** argv)
{
	int n;
	cin>>n;
	vector<pair<int,int> > points;
	for(int i=0; i<n; i++)
	{
		int x,y;
		cin>>x>>y;
		points.push_back(make_pair(x,y));
	}
	sort(points.begin(), points.end(), cmp);
	int max_x = 0;
	vector<pair<int, int> >::iterator it;
	for(it=points.begin(); it!=points.end(); it++)
	{
		if(it->first > max_x)
		{
			cout<<it->first<<" "<<it->second<<endl;
			max_x = it->first;
		}
	}
	return 0;
}