Posted on 2010-03-21 00:36
王之昊 閱讀(219)
評論(0) 編輯 收藏 引用 所屬分類:
pku
這道題模擬，已知一個支點，去尋找下一個支點，累加這期間的角度直到轉到滿意的角度為止。把繞支點的轉動看成一個圓，把多邊形的每條線段看成障礙物。現在來考慮一些特殊位置。
出題者應該會避免相切的數據。和當前木棍在同一直線上的特殊點，一種可以根據線段的中心確定它會不會阻擋。
另外一種連中心也在同一條直線上。這時認為在有木棍實體的那側的特殊點不會阻擋，而另一側會。
總的來說，障礙物（一條線段）他可能出現的位置是0~360。而難區分的是0度和360度。如果發現一個點落在0度或360度的位置時，通過判斷障礙物在左邊（包括平行的時候）還是在右邊來確定會不會阻擋。
還可以通過讓木棍轉動一個小的角度，看一下是遠離障礙物，還是和障礙物相交來確定是否會阻擋。