离大海最远点在哪里?

2015年2月3日6,4750

http://218.5.5.242:9014/problem.asp?id=1678

题目描述

遥远的海上有一座岛屿,这个岛屿的轮廓是一个凸多边形,把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远,这地点应在哪里?

岛上居民们习惯地把岛上某个点到岛屿的各条海岸线(即各边)距离中最小者看成该点到大海的距离。如下图所示,点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB,BC,CD,DE,EA的距离。

现在,给您N个点来描述这个凸多边形海岛,岛上的居民请您帮他们计算出岛上距离大海最远的点到大海的距离。

输入

第一行一个正整数N(N<=200000),表示凸N边形的边数,以下N行每行两个整数(xi,yi),表示凸N边形的每个点的坐标,坐标按逆时针方向给出,且|xi|,|yi|<=1011.

输出

    一行一个实数d,表示所求距离。d保留6位小数。答案保证c/c++的double和pascal的extended可存。

样例输入

4 1 1 0 1 0 0 1 0

样例输出

0.500000

提示

数据范围:N<=200000|xi|,|yi|<=1011

题解

算法1:二分将半平面推进,判交集是否为空

但是使用半平面交做法的话,不仅答案精度不够,还有可能超时

只能通过部分数据

算法2:实际上。我们只要知道最后凸多边形面积变为0的时候,所有半平面向内平移了多少距离,那么,这个距离就是答案。

凸多边形减小的过程,实质是一条边一条边减少,而且减少的那条边对小凸多边形的控制可以由其相邻的两条边取代,即每过一段时间,就减少了一条边的约束,直到最后剩下两条边。那么,我们只要知道在什么时刻,减少了哪条边就可以了。因此,对于每一条边i,我们维护其在什么时刻被相邻的两条边取代,记为ti。

1.这条边相邻两边平行,则ti为两边距离的一半

2.这条边相邻两边不平行,ti为其相邻两角的角平分线交点到它的距离

那么,每次对于小凸多边形,在所有边中取最小的ti,将所对应的边删除,并维护相邻的两条边被删除的时间,就可以了。

实现使用堆+双向链表

半平面交

pq+双向链表

 

 

avatar
  Subscribe  
提醒