题目:传送门

题意:平面上有n个点,问是否存在四个点 (A,B,C,D)(A<B,C<D,ACorBD)使得AB的横纵坐标差的绝对值的和等于CD的横纵坐标差的绝对值的和n<10^5,点的坐标值m<10^5

题解:表面上这道题复杂度是O(n^2)会超时的,而实际上这些坐标差绝对值的和最大是2*10^5,所以复杂度不是O(n^2),而是O(min(n^2,m)),这就是著名的鸽笼原理

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int abs(int i) {
if(i<) return -i;
return i;
}
int cal(int x,int y,int x1,int y1){
return abs(x-x1) + abs(y-y1);
}
int main()
{
int n,m,T,x[],y[];
bool a[];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(a,,sizeof(a));
for(int i=;i<n;i++) {
scanf("%d%d",&x[i],&y[i]);
}
for(int i=;i<n;i++)
for(int j=i+;j<n;j++) {
int t=cal(x[i],y[i],x[j],y[j]);
if(a[t]) {
puts("YES");
goto NEXT;
}
a[t]=true;
}
puts("NO");
NEXT:;
}
return ;
}

最新文章

  1. yum源安装Mysql
  2. XMPP框架下微信项目总结(1)环境配置
  3. 常用vim设置
  4. form和validate示例
  5. 使用labview对kinect进行开发
  6. Cxf + Spring3.0 入门开发WebService
  7. HDU 4280 Island Transport(网络流)
  8. Weekend counter
  9. Winsock编程基础介绍 .
  10. 联想K82------智能电视行业的野蛮入侵者
  11. C++达到String分类
  12. Java学习之旅基础知识篇:面向对象之封装、继承及多态
  13. CentOS7 安装 jexus-5.8.2-x64
  14. ad 线束和网络
  15. 强大的xargs
  16. Stm32常见英文缩写
  17. django之Session、Cookie
  18. Chrome disable cache &amp; clear memory cache
  19. html的css选择器
  20. Jmeter-Ant 生成测试报告

热门文章

  1. OpenCV imread读取图片,imshow展示图片,出现cv:Exception at memory location异常
  2. nginx反向代理、优化
  3. HDU 5074 Hatsune Miku(2014鞍山赛区现场赛E题)
  4. 笔记(一):ES6所改良的javascript“缺陷”
  5. 通过Unity3d创建二维码(利用zxing2.2)
  6. navigationcontroller手势翻页和navigationbar
  7. 在Fedora 20 上安装Mysql并初始化root密码
  8. linux shell脚本常用语句
  9. BZOJ 2412: 电路检修
  10. 微型Http服务器Tiny Http Server