3525 Most Distant Point from the Sea

Posted on 2010-03-15 23:12 王之昊阅读(177) 评论(0) 编辑收藏引用所属分类: pku

这道题用二分 + 半平面交去做可以. 但是不利于推广道凹多边形.
还有一种做法就是内切圆必然和多边形的某些边相切, 我们二分半径, 然后枚举两条相切的边(凹多边形也可能是顶点), 确定圆心, 再看多边形是否包含这个圆.
确定圆心的时候直接解方程就可以了.

只有注册用户登录后才能发表评论。


相关文章: 1444 Parallelepiped walk Cover an Arc 2284 That Nice Euler Circuit 3329 Twirl Around 3525 Most Distant Point from the Sea 3608 Bridge Across Islands 3675 Telescope 2932 Coneology 3410 Split convex polygon 3384 Feng Shui

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

岁月的童话