注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

波老师(teacher/1S/64M)  

2016-08-04 21:17:20|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

【题目描述】

波波老师是一个地理老师。有一天他上课的时候,他在地图上标记了N个点,第i个点在点(Xi,Yi)。他想知道,是否存在四个点(A,B,C,D)(A<B,C<D,AC或者BD),使AB之间的曼哈顿距离和CD之间的曼哈顿距离相等。

如果存在这样的四个点,输出YES,否则输出NO

 

【输入格式】

输入文件第一行是一个T(T50),表示有T组数据。

接下来有T组数据,每组数据第一行是两个整数N(<100000),M(<100000),表示点的个数以及点的坐标的边界,然后有N行,第i行有两个整数Xi,Yi表示第i个点的坐标(Xi,Yi)(0Xi,YiM)

 

【输出格式】

输出文件有T行,每一行为YES或者NO

=================================================

    先来普及一下:曼哈顿距离(点A到点B的曼哈顿距离为|Ax-Bx|+|Ay-By|),呃,那也不大啊。最多……200000。然后我果断用了个数组计数,一但出现就记一下,两次就退掉,发现这样总能很快,AC(虽然做的时候没用scanf,TLE了一个点)。然后一直不懂,TMK最后说是鸽巢原理,仔细一想,最多……200000,虽然点对能计算出n^2种距离,但距离最多有200000种,所以时间复杂度为O(min(n^2,2m)),原来,一直不重视的m,成了决定时间的一方面重要因素。

    这道题让我长见识了,像这种只要存在就可以的题,会往鸽巢原理想一想。

========================================================

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

const int MLn=100010;
const int MLm=1000010;

struct Tpoint { int x,y; }a[MLn];

bool f[MLm];

int main()
{
freopen("teacher.in","r",stdin);
freopen("teacher.out","w",stdout);

int t; scanf("%d",&t);

for ( ; t>0; t--)
{
memset(a,0,sizeof a);
memset(f,0,sizeof f);

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

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

bool ff=1;

for (int i=0; i<n && ff; i++)
for (int j=i+1; j<n; j++)
{
int d=abs(a[i].x-a[j].x)
+abs(a[i].y-a[j].y);
if (f[d])
{
cout<<"YES";
ff=0;
break;
}
f[d]=1;
}

if (ff) cout<<"NO";
cout<<endl;
}

return 0;
}


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018