J: 点
J: 点
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
平面上有 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从小到大排序，如果y相同的就把y小的排到前面，然后对每个点的y从前往后找，如果后面有的点的y大于这个点的y，那么这个点就会被覆盖，直接break到下一个循环再判断，如果没有比这个y还打的y了就输出这个点。
如果只是求二维偏序符合的点的个数有多少个的话可以采用树状数组求逆序对数量的方法来优化，排好x之后只用树状数组维护y的逆序对个数就好了
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,m;
int t;
double a,b;
struct node
{
int x,y;
}dian[maxn];
bool comp(node a,node b)
{
if(a.x==b.x)
return a.y<b.y;
else
return a.x<b.x;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>dian[i].x>>dian[i].y;
}
sort(dian,dian+n,comp);
for(int i=0;i<n;i++)
{
int flag=1;
int z=dian[i].y;
for(int j=i+1;j<n;j++)
{
if(dian[j].y>z)
{
flag=0;
break;
}
}
if(flag==1)
{
cout<<dian[i].x<<" "<<dian[i].y<<endl;
}
}
}
return 0;
}
评论