灯塔

时间限制: 1000 ms         内存限制: 131072 KB

【题目描述】
大洋上共有 N 个岛屿，从 1 到 N 标号。与广袤的大海相比，我们可以认为每个岛都只是平面上的一个点。给定所有岛屿的笛卡尔坐标，坐标系 X 轴指向东，Y 轴指向北。

你需要照亮所有的岛屿。为此，你可以在某些岛屿上修建灯塔。每个岛屿至多只能建一座灯塔。每个灯塔可以照亮以它为原点的坐标系的一个象限，即东北、西北、西南、东南的其中之一。注意如果一个岛屿落在光照的边缘，也被认为被照亮了，这意味着修建灯塔的岛屿总是被照亮的。

请你找出一个照亮所有岛屿所需灯塔数（记为 L）最小的方案。

【输入】
输入数据第一行包含一个整数 T，表示数据组数。

接下来是 T 组数据。 每组数据第一行包含一个整数 N，表示岛屿数量。

接下来的 N 行，每行包含两个整数 Xi 和 Yi，表示各岛屿的坐标。

【输出】
对于每组数据，输出一行包含需要的灯塔数量 L。

【输入样例】   
1   
4  
5 0  
-5 0  
0 5  
0 -5  
【输出样例】  
2  
【提示】  
【数据规模】  

对于20%的数据，1≤N,T≤10;

对于100%的数据，1≤T≤1000，1≤N≤10^5，0≤|Xi|,|Yi|≤10^9，∑N≤5×10^5。

题目如上,请问有没有原题/非常类似的题,内部OJ上改了半天都被卡第二个测试点,就是不知道错哪(看不到测试数据).教练说这道题就是找一下四个方向的极点,如果有一个极点是在左上/右上/左下/右下,就输出1,否则输出2.可是小蒟蒻就改不对,代码如下:

#pragma GCC optimize(3,"Ofast","inline")//日常优化
#include<bits/stdc++.h>//标准头文件
using namespace std;//必要格式
int main()//烤main包
{
 	ios::sync_with_stdio(false);//加快速度
 	long long t;cin>>t;//一共t组数据 
 	for(long long i=1;i<=t;i++)//每一组数据中 
 	{
 		long long k;cin>>k;//一共k个点 
 		long long n,s,w,e,nk=-99999999,sk=99999999,wk=9999999999,ek=-999999999;//记录最上,最下,最左,最右的点,及各自极点坐标 
 		for(long long j=1;j<=k;j++)//输入每个点的坐标 
 		{
 			long long x,y;cin>>x>>y;//输入坐标 
 			if(y>nk)//如果这个点比已知最上点更上 
 			{
 				n=j;//记录上极点 
 				nk=y;//更新上极点坐标 
 			}
 			if(y<sk)//如果这个点比已知最下点更下 
 			{
 				s=j;//记录下极点 
 				sk=y;//更新下极点坐标 
 			}
 			if(x<wk)//如果这个点比已知最左点更左 
 			{
 				w=j;//记录左极点 
 				wk=x;//更新左极点坐标 
 			}
 			if(x>ek)//如果这个点比已知最右点更右 
 			{
 				e=j;//记录右极点 
 				ek=x;//更新右极点坐标 
 			}
 		}
 		if(n==w/*左上*/||n==e/*右上*/||s==w/*左下*/||s==e/*右下*/||k<=3)cout<<"1"<<endl;//如果有两个极点是相同的,就只需要一个极点就可以照完 
 		else cout<<"2"<<endl;//否则要两个 
 	}
	return 0;//祈祷AC
}

大佬能看一下吗,蟹蟹
大佬如果想测小蒟蒻可以帮忙提交一下看是否正确