Brief description:
。。。船长遥 ( Captain Faraway ) 和他著名的圆形船支科洛号 ( Circular Ship Kolobok ),被困在了他刚刚发现的一些群岛的周围,所有的岛屿包括船支都被描述成圆形,题目询问是否可以安全的离开这片海域。。。
Analysis:
… 判断圆交、注意外切的不算。。建图后求封闭区域。。之后判断出发点是否在多边形内。。
(在 dfs 树中能快速求出 lca 的话。。这一步应该能 O(1) 。。
External link:
http://acm.sgu.ru/problemset.php?contest=0&volume=1
http://hi.baidu.com/sabbah/item/f81cf5c01617472e47d5c048