hdu_5762_Teacher Bo(鸽笼原理)

题意：

给你n个点，问你能否找到两对点的曼哈顿距离相等

题解：

最开始看到这题，看数据以为要向nlogn的复杂度发展，结果经验误导了自己，我们仔细观察可以发现，题目给的点的坐标范围为0~1e5，说明所有的点对的曼哈顿距离的种数不会超过2*m+1，意思就是n个点的曼哈顿距离的范围为0~200000，所以如果点对的个数大于2*m+1，那么必定会有重复的曼哈顿距离，也就是由两对点的曼哈顿距离相同，所以特判后直接暴力，复杂度不超过10W.

 #include <cstdio>

 #include<cstring>

 int abs(int a){return a>?a:-a;}

 const int N=1E5+;

 struct point{int x,y;};

 point a[N];

 bool vis[N*];

 int main()

 {

     int n,t,m;

     scanf("%d",&t);

     while(t--)

     {

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

         long long nn=n;

         for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);

         if(nn*(nn-)/>*m+){puts("YES");continue;}

         memset(vis,,sizeof(vis));

         int fg=;

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

         {

             if(fg)break;

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

             {

                 int dis=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);

                 if(vis[dis]){fg=;break;}else vis[dis]=;

             }

         }

         if(fg)puts("YES");else puts("NO");

     }

     return ;

 }

巴特西

hdu_5762_Teacher Bo(鸽笼原理)

最新文章

热门文章