Teacher Bo

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5762

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

Hint

题意

让你找到两组不同的点，使得他们的曼哈顿距离相同

题解：

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

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

一组数据的时间复杂度 O(\min{N^2,M})

,M}) .

代码

#include <bits/stdc++.h>

using namespace std;

const int N=100010;

int x[N],y[N],vis[N*4];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        int flag=1,mx=m*4+10,cnt=0;

        for(int i=0;i<=mx;i++) vis[i]=0;

        for(int i=0;i<n;i++)

            scanf("%d%d",&x[i],&y[i]);

        for(int i=0;i<n;i++)

        {

            for(int j=i+1;j<n;j++)

            {

                if(cnt>mx)

                {

                    flag=0;

                    break;

                }

                if(vis[abs(x[i]-x[j])+abs(y[i]-y[j])])

                {

                    flag=-1;

                    break;

                }

                vis[abs(x[i]-x[j])+abs(y[i]-y[j])]=1;cnt++;

            }

            if(flag<1) break;

        }

        if(flag==-1) printf("YES\n");else printf("NO\n");

    }

    return 0;

}

巴特西

hdu 5762 Teacher Bo 暴力