灯塔-牛客

本文主要是介绍灯塔-牛客，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Z市是一座港口城市，来来往往的船只依靠灯塔指引方向。
在海平面上，存在n个灯塔。每个灯塔可以照亮以它的中心点为中心的90°范围。特別地， 由于特殊限制，每个灯塔照亮范围的角的两条边必须要么与坐标轴平行要么与坐标轴成45°。 由于经费限制，Z市的灯塔只能被点亮一座。你需要求出在这种情况下，是否存在一座灯塔能够照亮Z市的所有灯塔。

输入描述:

第一行一个整数T,表示数据组数。
对于每组数据，第一行一个整数n，表示灯塔的数量。
接下来n行，每行两个整数xi,yi，表示第i座灯塔的坐标点。

输出描述:

如果存在一座灯塔能够照亮Z市的所有灯塔则输出Yes，否则输出No（区分大小写）。

示例1

输入

复制

2
4
1 1
1 2
2 1
2 2
5
4 7
0 4
7 3
3 0
3 4

输出

复制

Yes
No

备注:

n≤1000000,T≤10,0≤|xi|,|yi|≤109

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
using namespace std;
int t,n;
struct fun{double x,y;
}f[1000005];int fun(){double minx=f[0].x,miny=f[0].y,maxx=f[0].x,maxy=f[0].y;for(int i=1;i<n;i++){minx=min(minx,f[i].x);miny=min(miny,f[i].y);maxx=max(maxx,f[i].x);maxy=max(maxy,f[i].y);}for(int i=0;i<n;i++){if((f[i].x==minx||f[i].x==maxx)&&(f[i].y==miny||f[i].y==maxy))return 1;}return 0;
}int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lf %lf",&f[i].x,&f[i].y);if(fun()){printf("Yes\n");continue;}for(int i=0;i<n;i++){double xx=f[i].x+f[i].y;double yy=f[i].x-f[i].y;f[i].x=xx;f[i].y=yy;}if(fun()){printf("Yes\n");}elseprintf("No\n");}return 0;
}

 

这篇关于灯塔-牛客的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---