Teacher Bo

Time
Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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

Sample Output

YES

NO

这题实在找不到什么方法做了，只能暴力试试，可是居然卡在曼哈顿路径的概念上了；

我们以为是两点间的距离公示，然后用hypot（，）WA了两遍，之后两小时一直像睡着了了一样；

早知道百度一下概念，也不会耽误这么多时间，最后两分钟改了求距离那里直接交一发A了；

#include<bits/stdc++.h>

using namespace std;

const int N=100000+10;

struct node

{

    int x,y;

} a[N];

int cmp(node a,node b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    while(t--)

    {

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

        set<double>m;

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

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

        sort(a,a+n,cmp);

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

        {

            if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y)

            {

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

                    a[j]=a[j-1];

                n--;

                i--;

            }

        }

        int f=0;

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

        {

            if(f) break;

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

            {

                double dis=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);//主要还是概念没搞清，其他地方全正确；

                if(m.find(dis)!=m.end())

                {

                    f=1;

                    break;

                }

                m.insert(dis);

            }

        }

        if(f) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}

同！志！仍！需！努！力！

秒客网

2016 Multi-University Training Contest 3-1011.Teacher Bo，暴力！

Teacher Bo

相关文章