POJ3703寻找平面上的极大值点--贪心+栈水题（二）

描述在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x>=a,y>=b;
用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。
给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。
编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。
本题规定：n不超过100，并且不考虑点的坐标为负数的情况。输入输入包括两行，第一行是正整数n，表示是点数，第二行包含n个点的坐标，坐标值都是整数， 坐标范围从0到100，输入数据中不存在坐标相同的点。输出按 x轴坐标最小到大的顺序输出所有极大点。
输出格式为:(x1,y1),(x2,y2),...(xk,yk)
注意：输出的每个点之间有","分隔,最后一个点之后没有",",少输出和多输出都会被判错样例输入

5 
1 2 2 2 3 1 2 3 1 4

样例输出

(1,4),(2,3),(3,1)

提示

本题收获：1.知道了sort和qsort函数中cmp的使用，请看大神的文章2.利用栈的特性，将结果按x从小到大的顺序排列。以下是代码：

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef struct Node
{
	int x, y;
}Node;
Node _Node[105];
stack<Node> s;
int cmp(Node a, Node b)//先安x值由大到小顺序排序，再按照y值从大到小排序
{
	if (a.x > b.x) { return 1; }
	else if (a.x == b.x)
	{
		if (a.y > b.y) { return 1; }
		else { return 0; }
	}
	else { return 0; }
}
int n;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> _Node[i].x >> _Node[i].y;
	}
	sort(_Node, _Node + n, cmp);
	for (int i = 0; i < n; i++)
	{
		int FLAG = 0;//没有能覆盖它的点，这个值为0
		int a = _Node[i].x;
		int b = _Node[i].y;
		for (int j = 0; j < i; j++)//从以前的点中，寻找可能覆盖_Node[i]的点
		{
			if (_Node[j].x >= a && _Node[j].y >= b)
			{
				FLAG = 1;//找到了能覆盖_Node[i]的点
				break;//退出寻找过程
			}
		}
		if (FLAG == 1) { continue; }//找到了覆盖_Node[i]的点，跳出循环
		else//真主说：_Node[i]确实是极大值点了 
		{  
			s.push(_Node[i]);//加入栈顶
		}
	}
	if (s.size() == 1)
	{
		cout << "(" << s.top().x << "," << s.top().y << ")";
	}
	else
	{
		cout << "(" << s.top().x << "," << s.top().y << ")";
		s.pop();
		while (!s.empty())
		{

			cout <<","<< "(" << s.top().x << "," << s.top().y << ")";
			s.pop();
		}
	}

	system("pause");
	return 0;
}