Felicia

2007年9月23日

[计算几何]pku3384
     摘要: 强烈推荐此题。半平面交算法的一个应用。
具体做法是，把多边形的每条边向内平移r单位长度，用这些线段所在直线和原多边形作半平面交，得到的区域就是半径为r的圆放入多边形的可行域。可以证明这个区域一定是凸的，或者退化为一条线段，或一个点。那么，我们就可以在这个区域上求最远点对啦。
我的做法是O(n^2)的。应该存在O(nlogn)的做法，因为都是凸多边形，每次半平面交只有最多两个交点，可二分，而最后的求最远点对可以旋转卡壳。比赛的时候时间少，就写了个暴力O(n^2)的。

  阅读全文
posted @ 2007-09-23 16:19 Felicia 阅读(786) | 评论 (0) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia