求简单多边形的内切圆半径 POJ 3525

题目 大意：给定一个简单多边形，求多边形内的一点到所有边界的最小距离最大。题目事实上就是叫你求这个简单多边形的内切圆半径。

我的做法是二分内切圆半径，然后通过对简单多边形半平面交判定实现的。在判断结束时，我出现了点逻辑性错误，居然求点到边的距离，那么我就对原简单多边形做半平面交，直至这个交后新简单多边形面积为很小即可，结果TLE很多次，开始还以为是算法角度问题引起二分处死循环。事实上，我只需用普通的判断二分内切圆半径的上下界只差小于一定值即可，改之AC了。一次经验教训。算法复杂度为二分次数乘 O(n^2)，基本上可以说是O(n^2).

二分内切圆半径和简单多边形半平面交主要实现如下：

//二分内切圆半径 while (up - low > EPS) {memcpy(new_poly, poly, sizeof (poly[0]) * (n + 1));nn = n;mid = (up + low + EPS) * 0.5;//O(n^2)实现简单多边形半平面交for (i = 0; i < n; ++i) {seg0.s = poly[i], seg0.e = poly[i + 1];get_dis_parall(mid, seg0, seg1, seg2);if (cross(poly[i + 1] - poly[i], seg1.s - poly[i]) > -EPS)st =

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！