icpcarchive6041 Retrenchment

传送门
雅加达的D,今天在机场滞留的时候写的……

【题意】

给n个点,R个区域(闭合简单多边形),每次询问某个区域内离给定点(qx, qy)的最近点与次近点分别是谁。

【算法】
求平面欧几里得距离最近点显然KDTree可以搞的。
具体就先暴力射线法判点在简单多边形内,然后把区域点集塞进KDTree里面,对于询问,用经典方法找离(qx, qy)最近的点。然后把这个点删除,再找次近点。输出以后把这个删掉的点插回去就好了。因为每次都是对静态的删除以及复原,所以直接加标记lazy delete就好了。
【时间复杂度】
$$O(Q \sqrt{n})$$
KDTree还是很快的……

【空间复杂度】
$$O(n)$$
【Note】
太圡了,WA了挺久的,因为define sqr(x) ((x) * (x)),然后x是int,然后就爆了……以后得注意了
【代码】
https://gist.github.com/4626176

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注