SGU(nlogn半平面交)解题报告.docVIP

SGU332 解题报告 ——Gen SGU332问题： 逆时针给出一个凸多边形的各点坐标，求它的内切圆半径。凸多边形的内切圆定义为圆心在凸多边形内，可与凸多边形若干条边相切，半径最大的圆。 点数=10000 坐标绝对值不超过pow(10,7) 思路： 将所有边规定方向，每条边视作一个半平面，按极角排序，由于是凸多边形，所以极角相同者可以简单地只保留一个。 //假设半平面的集合为 hplane[num_hplane]; 遍历内切圆半径的值R { 把每个半平面向内平移R的长度 使用一个双端队列(deque)，依次向首部加入hplane[0],hplane[1]。 for(i=2;inum_hplane;i++) { while(deque顶端的两个半平面的交点在hplane[i]外) {删除deque顶端的半平面} while(deque底部的两个半平面的交点在hplane[i]外) {删除deque底部的半平面} if(deque非空) 将hplane[i]加入deque顶端 else 取新的R值尝试 } //删除两端多余的半平面 while(deque顶端的两个半平面的交点在底部半平面外) {删除deque顶端的半平面} while(deque底部的两个半平面的交点在顶端半平面外) {删除deque底部的半平面} 如果最后剩下的半平面在3个以上，取新的R值尝试 下面说明怎么具体实现上述思路： 如何遍历半径R 半平面的表示 半平面平移的几何表示 取舍半平面的标准 二分法，取上下界分别为high=1e07和low=0，R=(high+low)，以及一个极小值eps=1e-8.如果R使得最终交得的半平面数在3个以上，则low=R，继续循环; 否则high=R，继续循环. 直到high-low=eps. 结构体 struct point{double x,y;} struct HalfPlane{point p1,p2;} 如上图，一个半平面p1,p2表示以右手拇指朝向纸外，四指从p1指向p2,在直线p1p2手掌外方向的平面部分. 为易于理解，此处半平面的极角定义在 [0,2π）内，下面引理请自行验证。 如果半平面的倾角为θ∈[0,2π），则其向内平移长度R 可以表达为 p1.x+=R*sinθ,p1.y+= －R*cosθ p2.x+=R*sinθ,p2.y+= －R*cosθ 假设deque支持以下8个操作： push_front(int m) ，把元素m放入队列首部 push_back(int m) ，把元素m放入队列尾部 pop_front()，删除队列首部 pop_back()，删除队列尾部 front()，返回队列首部元素 back()，返回队列尾部元素 next_to_front()，如果队列长度≥2，返回队列首部第二个元素 next_to_back()，如果队列长度≥2，返回队列尾部第二个元素 以加入半平面的过程为例。一开始我们向队列加入倾角最小的两个半平面，然后按倾角 从小到大加入半平面并维护deque。 PS:为了叙述方便，deque的元素类型是int，装入的是排序后的半平面的编号 假设访问的半平面编号为current，deque首部两个半平面的交点为intersection1，尾部两个半平面的交点为intersection2，current半平面的起点为p1,终点为p2. 如果intersection在current半平面之外，则删去deque首部半平面，不断重复这一过程 while p1,p2×p1,intersection1 0 ，deque.pop_front() 类似地设尾部两个半平面的交点为 another_intersection. while p1,p2×p1,intersection2 0 ，deque.pop_back() 直到交点集中没有在当前半平面外的点，再把当前半平面加入deque中 if(deque is not empty after steps above) deque.push_front(current); else terminate the loop of testing radius 删除多余半平面的步骤类似。 叉积的值是向量，这里与0比较用的是坐标交叉相乘后取差的值。 下面是我在SGU提交的代码，由于SGU的数据比较严格，我作了一点优化，用另一个双端队列把交点集保存起来，以避免每次重复求交点浪费时间。 #includ