Teacher Bo
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1014 Accepted Submission(s): 561
Problem Description
Teacher BoBo is a geography teacher in the school.One day in his class,he marked N points in the map,the i-th point is at (Xi,Yi).He wonders,whether there is a tetrad (A,B,C,D)(A<B,C<D,A≠CorB≠D) such that the manhattan distance between A and B is equal to the manhattan distance between C and D.
If there exists such tetrad,print "YES",else print "NO".
Input
First line, an integer T. There are T test cases.(T≤50)
In each test case,the first line contains two intergers, N, M, means the number of points and the range of the coordinates.(N,M≤105).
Next N lines, the i-th line shows the coordinate of the i-th point.(Xi,Yi)(0≤Xi,Yi≤M).
Output
T lines, each line is "YES" or "NO".
Sample Input
2
3 10
1 1
2 2
3 3
4 10
8 8
2 3
3 3
4 4
3 10
1 1
2 2
3 3
4 10
8 8
2 3
3 3
4 4
Sample Output
YES NO
#include<iostream>
#include<stdio.h>
#include<set>
#include<math.h>
using namespace std;
const int maxx = ;
set<int> hav;
int px[maxx];
int py[maxx];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
hav.clear();
scanf("%d%d",&n,&m);
for(int i=; i<n; i++ )
{
scanf("%d%d",px+i,py+i);
}
int flag=;
for(int i=; i<n-; i++)
{
for(int j=i+; j<n; j++)
{
int dis=abs(px[j]-px[i])+abs(py[j]-py[i]);
if(hav.count(dis))
{
flag=;
break;
}
else
{
hav.insert(dis);
}
}
if(flag)
{
break;
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return ;
}
考虑一种暴力,每次枚举两两点对之间的曼哈顿距离,并开一个桶记录每种距离是否出现过,如果某次枚举出现了以前出现的距离就输 YESYES ,否则就输 NONO .
注意到曼哈顿距离只有 O(M)O(M) 种,根据鸽笼原理,上面的算法在 O(M)O(M) 步之内一定会停止.所以是可以过得.
一组数据的时间复杂度 O(\min{N^,M})O(min{N^ ,M}) .