Andrew Stankevich Contest #32 Problem C 二维平面反演, 动态凸包

地址

给定n(1 ≤ n ≤ 105)个点,一个点(x, y)是好的,当且仅当以(0, 0) – (x, y)为直径的圆内不包含其它好的点。(x, y)皆是原点外的整点。0 ≤ |x|, |y| ≤ 30000。输出所有好的点。

因为题目的这个递归定义,显然应该按(x, y)到原点的距离从小到大排序,然后每次插入点之前检测一下,如果圆内没有点就插入,否则就拒绝。

这题因为给的都是整点,范围又小,构造不出大数据,直接用这个方法是能过的- -b……但是显然这不是一个令人满意的做法。

因为所有的圆都过原点,很容易想到对整个平面进行反演

这样圆都会变成一条直线,而“在圆内”反演后就会变成“在这个直线的一侧”(与原点相反的一侧)。

于是反演过后变成这样一个问题:每次给一条直线,问是否之前插入的点都在这个直线的某一侧。如果是,把这个点插入点集。

那么如何快速判断一个点集是否全都在一条直线的某一侧?

不妨把直线看成一个向量,容易想到如果对这些点集求出一个凸包,那么凸包上向量的极角是单调的,在上面找到出与当前直线对应向量最相近的两条边,中间的那个顶点就是在该直线法向量方向看最远的点。于是只要判断这个点是否符合条件就可以了。

剩下的问题就是给定一个凸包,每次有插入操作,怎么快速动态地维护这个凸包?

对于这个单调的东西,手写一个平衡树维护凸包顶点肯定是能做的,但是也可以偷懒利用STL的set。但是这里有个问题,到底是维护set < Line > set < Point >?对于判断是否在直线一端的部分,只有存Line能做,对于后面凸包的动态插入,只有Point能做……于是只能两个都维护了,在插入凸包的时候两个一起操作。

这里还有一个小技巧,因为叉乘只能判左还是右,超过180°的很容易写出奇怪的情况,于是动态凸包我是通过上凸壳和下凸壳来维护的。但是这样就要写两种情况,一个好的方法是对于下凸壳,直接左右翻转,上下翻转(也就是所有点的坐标都取负),这样就变成同样维护上凸壳了。

时间复杂度:O(n lg n)
空间复杂度:O(n)

PS.反演精度比较坑爹,建议使用相对误差进行几何上的判定。

代码