05 Apr 10 HDOJ Monthly Contest – 2010.04.04 Problem 1003 Point

http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1003&cid=276

题目大意就是用下面的距离定义来求每一个点的最近点对。

Distance (A, B) = max (|Ax – Bx|, |Ay – By|)

这题是我最初给我们学校去年的区域赛准备的题目。说一下做法：对于每一个点，先二分答案，这样转化为判断是不是一个正方形内有点的问题。对于解决这个问题，用二维的线段树来解决。很多人对于二维线段树的理解就是把一维变成二维，空间复杂度从O(n)变成O(n^2)。其实不是这样的，复杂度为O(n^2)的线段树基本没有什么用处。

可以用变化一下的实现方法使得空间复杂度变成O(nlogn)。具体的实现方法可以参见我们学校的wiki上我贴的代码。

http://acm.whu.edu.cn/wiki/index.php/Point

Tags: HDOJ Monthly, 二维线段树, 计算几何

Filed in Iproblem

Reader's Comments

Anonymous | 06 Apr 2010 5:35 pm
Hi.你的代码的2维线段树的复杂度应该还是O(n^2)的空间复杂度的，刚开始从[-1000:1000]*[-1000:1000]的不断拆分，直到单位矩阵为止。

[Reply]
Anonymous Reply:
April 6th, 2010 at 7:03 pm
你应该没有理解我的代码。并非知道单位矩阵为止。要是空间复杂度这么高的话，早就爆掉了，那可不是1000是100000

[Reply]
Anonymous Reply:
April 6th, 2010 at 8:44 pm
说错了。。应该是O(range^2)的空间吧？我感觉你是要开完2000*2000的

[Reply]
Anonymous Reply:
April 6th, 2010 at 9:11 pm
如我所说，是nlogn的空间。。与range没有关系，range很大的

[Reply]
sunhaowen | 20 May 2010 5:17 pm
你这题数据有点弱了，直接暴力就可以过啊

[Reply]
momodi Reply:
May 20th, 2010 at 5:19 pm
嗯。。暴力的方法太多了，当时出数据不知道该怎么出。。

[Reply]
Valium | 28 May 2010 4:32 pm
comment5, Rimonabant, Female Viagra, Viagra, Ambien, Accutane, Clomid, Valium,

[Reply]