某島

… : "…アッカリ~ン . .. . " .. .
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