Problem Description
Recently, Dave is boring, so he often walks around. He finds that some places are too crowded, for example, the ground. He couldn't help to think of the disasters happening recently. Crowded place is not safe. He knows there are N (1<=N<=1000) people on the
ground. Now he wants to know how many people will be in a square with the length of R (1<=R<=1000000000). (Including boundary).
Input
The input contains several cases. For each case there are two positive integers N and R, and then N lines follow. Each gives the (x, y) (1<=x, y<=1000000000) coordinates of people.
Output
Output the largest number of people in a square with the length of R.
Sample Input
3 2
1 1
2 2
3 3
Sample Output
3
题意:首先给你几个点,再给你个正方形边长,让你求出在以该边长为正方形最多能包含多少点。
思路:一开始听himdd学长讲了思路,说是用到了离散数学。。。很是纠结,,,不过上网看了看别人代码,大都是用枚举的方法,感觉挺不错的。先把所有点的纵坐标从小到大排序,然后在以每一点纵坐标为下边界,以该坐标+r为上边界,找出其所对应的横坐标,并记录,然后在把横坐标排序,以每一点的横坐标为左边界以该点的横坐标+r为右边界枚举,从而得出该正方形的可包含的最多的点。
代码:
分享到:
相关推荐
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest Problem Set
The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest 注意,解压密码是:3.1415926535897932384
THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE Onsite Contest Session 8:30am – 13:30pm, November 20th 2005 (GMT+8) <br>知道是什么了吧。。。
ACM/ICPC参赛者必备!模版库,数十页的C++代码,涵盖ACM/ICPC中出现的各种算法!此为吉林大学版,内容相对比较全,排版质量是各校的模板中最好的!
IOI/ACM/ICPC参赛人员的理想选择——《算法艺术与信息学竞赛》
acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 ...
ACM/ICPC大赛
ACM/ICPC中国*辽宁第二届大学生程序设计竞赛题目
搜索
acm/icpc算法集合。acm/icpc算法集合。acm/icpc算法集合。
2015-2016 ACM-ICPC Northeastern European Regional Contest 标程
ACM/ICPC World Finals 1990 task
ACM/ICPC2009 拉丁美洲区域赛 包含输入输出数据 题目PDF文档 详细解题报告+答案代码TXT文档 有一半是水题,2、3个比较难的 大家可以拿来做做 其中的输入输出数据,可以放到那个离线OJ系统去判断你的程序对错。(离线...
ACM/ICPC的教学与实践
动态规划——北京大学暑期课《ACM/ICPC竞赛训练》
浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料
2010年ACM/ICPC珠海区域赛决赛题目
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
ACM/ICPC模板 内容大概有这些 其他 --高精度模板 --RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --...
本代码包括了常见的ACM算法,并给出了详细地实现过程,并附上了ACM/ICPC 竞赛之STL。