题目 K ： 点

题目描述 

平面上有 n 个点(任意两点的横坐标与纵坐标都不会相同)，每个点向 x 轴 和 y 轴做垂线分别形成两个交点，两个交点和该点以及坐标原点构成一个矩形，并覆盖矩形内的点(在边缘上的点不算被覆盖)，请输出平面上所有一次也没有被覆盖过的点。

输入 

第一行一个正整数 T(T<=5)，表示共有 T 组数据。

每组数据的第一行一个正整数数 n(1<=n<= 200000),表示平面上有 n 个点。

接下来 n 行每行两个正整数 x,y(1<=x,y<= 1e9)表示一个点的横纵坐标。

输出 

按 x 轴坐标从小到大输出所有符合条件的点。

样例输入

1
5
8 1
17 5
9 6
12 11
13 7

样例输出

12 11
13 7
17 5

解题思路

这道题的难点在如何降低复杂度，否则会轻易的超时，其实还可以这样去解，我们对输入的坐标点从小到大排序(按照x)，那么我们就可以得到，这样我们将x已经约束，所以只需要看当前坐标的纵坐标只要小于最大值，那么这个点一定会被覆盖的，如果不好理解手动排序一下，很容易看出来。

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MAX_LEN 200005
using namespace std;


typedef struct POINT{
	int x;
	int y;
	bool isFill;
}Point;

int cmp(Point a, Point b)
{
	return a.x < b.x;
}


Point point[MAX_LEN];
int main()
{

	int t;
	scanf("%d\n",&t);
	while (t--)
	{
		int n;
		scanf("%d\n",&n);
		memset(point, 0, sizeof(point));

		for(int i=0; i<n; i++)
		{
			scanf("%d%d",&point[i].x,&point[i].y);
		}
		
		sort(point, point+n, cmp);//排序,按照x从小到大排序
		
		int x_min = 1e9 + 5;
		int y_max = 0;
		
		for(int i=n-1; i>=0; i--)//从大到小遍历,因为x已经被约束
		{
			if(point[i].x < x_min && point[i].y <y_max)//判断点是否被填充
			{
				point[i].isFill = true;//填充
			}
			
			x_min = min(x_min,point[i].x);//更新x_min
			y_max = max(y_max,point[i].y);//更新y_max
			
		}
		
		for(int i=0;i<n;i++)//因为是x从小到大输出
		{
			if(!point[i].isFill)//没有被填充
			{
				printf("%d %d\n",point[i].x,point[i].y);
			}
		}
	}
	return 0;
}