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
points in the map,the
-th point is at
.He wonders,whether there is a tetrad
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
-th point is at
.He wonders,whether there is a tetrad
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
. There are
test cases.
In each test case,the first line contains two intergers, N, M, means the number of points and the range of the coordinates.
.
Next N lines, the
-th line shows the coordinate of the
-th point.
.
. There are
test cases.
In each test case,the first line contains two intergers, N, M, means the number of points and the range of the coordinates.
.
Next N lines, the
-th line shows the coordinate of the
-th point.
.
Output
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的那个下标值,就找出了相同的。
代码:
1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<iomanip> 9 #include<queue> 10 using namespace std; 11 struct point 12 { 13 int x,y; 14 }; 15 int main() 16 { 17 int n,m,t; 18 cin>>t; 19 while(t--) 20 { 21 point p[100005]; 22 int dis[100005]; 23 cin>>n>>m; 24 for(int i=0;i<n;i++) 25 { 26 cin>>p[i].x>>p[i].y; 27 } 28 int flag=0; 29 memset(dis,0,sizeof(dis)); 30 for(int i=0;i<n;i++) 31 { 32 for(int j=i+1;j<n;j++) 33 { 34 int tem=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y); 35 if(dis[tem]==1) 36 { 37 flag=1; 38 break; 39 } 40 dis[tem]=1; 41 } 42 if(flag==1) 43 { 44 cout<<"YES"<<endl; 45 break; 46 } 47 } 48 if(flag==0) cout<<"NO"<<endl; 49 } 50 return 0; 51 }