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

Sample Output

YES
NO

Source

2016 Multi-University Training Contest 3

分析

考虑一种暴力,每次枚举两两点对之间的曼哈顿距离,并开一个桶记录每种距离是否出现过,如果某次枚举出现了以前出现的距离就输 YES ,否则就输NO .

注意到曼哈顿距离只有O(M) 种,根据鸽笼原理,上面的算法在O(M) 步之内一定会停止.所以是可以过得.

一组数据的时间复杂度 O(min{N²,M}) .

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<iostream>
#include<cstring>
#define MAXN 100005
using namespace std;
int n, m;
int vis[MAXN*10];
int x[MAXN];
int y[MAXN];
bool solv(){
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            int num = abs(x[i]-x[j])+abs(y[i]-y[j]);
            vis[num]++;
            if(vis[num]>1)
              return true;
        }
    }
    return false;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(vis,0,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i = 1;i <= n;i++){
            scanf("%d %d",&x[i],&y[i]);
        }
        if(solv())
          printf("YES\n");
        else
          printf("NO\n");
    }
    return 0;
}