某岛

… : "…アッカリ~ン . .. . " .. .
June 7, 2012

SGU 198. Get Out!

Brief description:

。。。船长遥 ( Captain Faraway ) 和他著名的圆形船支科洛号 ( Circular Ship Kolobok ),被困在了他刚刚发现的一些群岛的周围,所有的岛屿包括船支都被描述成圆形,题目询问是否可以安全的离开这片海域。。。

Analysis:

… 判断圆交、注意外切的不算。。建图后求封闭区域。。之后判断出发点是否在多边形内。。
(在 dfs 树中能快速求出 lca 的话。。这一步应该能 O(1) 。。

。。计算几何。(32ms+-…

。。。2 年前的代码。。。(WA 18.。。。

External link:

http://acm.sgu.ru/problemset.php?contest=0&volume=1
http://hi.baidu.com/sabbah/item/f81cf5c01617472e47d5c048