3525 Most Distant Point from the Sea
Posted on 2010-03-15 23:12 王之昊 閱讀(227) 評論(0) 編輯 收藏 引用 所屬分類: pku這道題用二分 + 半平面交去做可以. 但是不利于推廣道凹多邊形.
還有一種做法就是內(nèi)切圓必然和多邊形的某些邊相切, 我們二分半徑, 然后枚舉兩條相切的邊(凹多邊形也可能是頂點), 確定圓心, 再看多邊形是否包含這個圓.
確定圓心的時候直接解方程就可以了.
還有一種做法就是內(nèi)切圓必然和多邊形的某些邊相切, 我們二分半徑, 然后枚舉兩條相切的邊(凹多邊形也可能是頂點), 確定圓心, 再看多邊形是否包含這個圓.
確定圓心的時候直接解方程就可以了.