牛客网 Wannafly挑战赛21 灯塔
2024-09-29 22:38:36
Z市是一座港口城市,来来往往的船只依靠灯塔指引方向。
在海平面上,存在n个灯塔。每个灯塔可以照亮以它的中心点为中心的90°范围。特別地, 由于特殊限制,每个灯塔照亮范围的角的两条边必须要么与坐标轴平行要么与坐标轴成45°。 由于经费限制,Z市的灯塔只能被点亮一座。你需要求出在这种情况下,是否存在一座灯塔能够照亮Z市的所有灯塔。
在海平面上,存在n个灯塔。每个灯塔可以照亮以它的中心点为中心的90°范围。特別地, 由于特殊限制,每个灯塔照亮范围的角的两条边必须要么与坐标轴平行要么与坐标轴成45°。 由于经费限制,Z市的灯塔只能被点亮一座。你需要求出在这种情况下,是否存在一座灯塔能够照亮Z市的所有灯塔。
输入描述:
第一行一个整数T,表示数据组数。
对于每组数据,第一行一个整数n,表示灯塔的数量。
接下来n行,每行两个整数xi,yi,表示第i座灯塔的坐标点。
输出描述:
如果存在一座灯塔能够照亮Z市的所有灯塔则输出Yes,否则输出No(区分大小写)。
备注:
n≤1000000,T≤10,0≤|xi|,|yi|≤109
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ll long long
#define N 1000009
#define gep(i,a,b) for(int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
int t,n;
struct Node{
int x,y;
}nod[N],p[];
bool cmp1(Node a,Node b)
{
return a.x<b.x;
}
bool cmp2(Node a,Node b){
return a.y<b.y;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
gep(i,,n-){
scanf("%d%d",&nod[i].x,&nod[i].y);
}
sort(nod,nod+n,cmp1);
p[]=nod[];p[]=nod[n-];
sort(nod,nod+n,cmp2);
p[]=nod[];p[]=nod[n-];
if(p[].y==p[].y||p[].y==p[].y||p[].y==p[].y||p[].y==p[].y){
printf("Yes\n");
continue;
}
bool judge[]={,,,};
gep(i,,n-){
if(abs(nod[i].y-p[].y)>abs(nod[i].x-p[].x))
judge[]=;
if(abs(nod[i].y-p[].y)>abs(nod[i].x-p[].x))
judge[]=;
if(abs(nod[i].y-p[].y)<abs(nod[i].x-p[].x))
judge[]=;
if(abs(nod[i].y-p[].y)<abs(nod[i].x-p[].x))
judge[]=;
}
if(judge[]+judge[]+judge[]+judge[])
printf("Yes\n");
else
printf("No\n");
}
}
最新文章
- Node.js入门(一)
- Node.js入门:Hello World
- No handlers could be found for logger ";keystoneauth.identity.generic.base";
- bootstrap源码里的function加上了+号
- IEnumerable 和 IQueryable
- 转载:遍历Map的四种方法
- SQL Server里的 ISNULL 与 NULLIF
- POJ1459 最大网络流
- [BZOJ 1409] Password
- mac中如何卸载pkg包
- NOIP-火柴棒等式
- linux性能优化参数小节
- React 添加对 Less 的支持, 使用 create-react-app 脚手架
- PD915温度太高,通过设置BIOS降底CPU的核心电压来降温。
- Python3基础 list enumerate 将列表的每个元素转换成 带索引值的元组
- CF981D Bookshelves
- 《Linux 性能及调优指南》2.4 基准工具
- WPF和js交互 调用窗体中的方法
- iOS 设备屏幕上实时打印 Log 的小工具
- Sqlserver 数据库、表常用查询操作