Teacher Bo
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1052 Accepted Submission(s): 582
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".
points in the map,the i
-th point is at (X
i,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)
. 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".
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
Sample Output
YES
NO
Author
绍兴一中
Source
Recommend
题意：
给出若干组点的坐标，求这中间有没有两组曼哈顿距离相同的坐标。
思路：
题目中X，Y都小于M，就可以用每一种曼哈顿距离作为数组的下标，并把数组标记为1，暴力出数组值为1的那个下标值，就找出了相同的。
代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
using namespace std;
struct point
{
int x,y;
};
int main()
{
int n,m,t;
cin>>t;
while(t--)
{
point p[];
int dis[];
cin>>n>>m;
for(int i=;i<n;i++)
{
cin>>p[i].x>>p[i].y;
}
int flag=;
memset(dis,,sizeof(dis));
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
int tem=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
if(dis[tem]==)
{
flag=;
break;
}
dis[tem]=;
}
if(flag==)
{
cout<<"YES"<<endl;
break;
}
}
if(flag==) cout<<"NO"<<endl;
}
return ;
}