题意:
(n) 和 (m),(n) 代表 (n(x,y))个点,(x) 和 (y) 的范围不会大于 (m),让你求这n个点之间的曼哈顿距离有没有重复的,有的话就输出 (“YES”),没有的话就输出 (“NO”)。
数据范围:(N,M≤10^5)
分析:
一开始被数据范围吓到了,但这道题其实就是暴力。因为曼哈顿距离最大为 (2*m),根据鸽巢原理,即可判断。
一般鸽巢原理的题都是先确定一个范围,然后根据定理直接求解。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int x[N],y[N];
bool vis[N<<1];
bool solve(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int t=abs(x[i]-x[j])+abs(y[i]-y[j]);
if(!vis[t])
vis[t]=1;
else
return 1;
}
}
return 0;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<=2*m;i++)
vis[i]=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
if(solve(n))
printf("YES
");
else
printf("NO
");
}
}