wannafly cap day3 計算幾何選講

Airport Construction

wf2017 A

1. 直線打斷多邊形

2. 點在多邊形内部

   O(n^4)

點在多邊形内，判斷點和線段交點，交線上段端點，線段上向下的點，cnt+1，否則cnt-1。

Castle

2018SDOI

Getting Lost

CCPC qinghuangdao

摳關鍵點跑最短路

如何摳關鍵點？

考慮幾何對象

點到圓，有切線

圓到圓，四種切線

一個圓心在另一個内部，與一個圓心在另一個圓心外部，總之就是相切。

外公切線轉化成從O1點向另外的O2圓心，r2-r1半徑的圓做切線，然後平移切點。

内切同理，半徑r1+r2的切

障礙圓阻隔了安全區…

變成了吃豆人><

Cornering at Poles

2014TOKYO

點變圓，圓變點，摳關鍵字跑最短路