顯示包含「Visibility」標籤的文章。顯示所有文章
顯示包含「Visibility」標籤的文章。顯示所有文章

2010年5月20日星期四

PKU 3703 Intuition of Escape



題意
二維場景內
給定一個 半徑 = R,位置 = (0,0) 的圓
及 N 個多邊形障礙物
問,是否在存一個移動方向,使得當圓形以直線前進時
不會觸碰這些障礙物

分析
算法大約都是枚舉(離散的)移動方向/角度 - angle[M]
然後逐一判斷是否可行

有關「觸碰」的限制
雖然可以 ± Epsilon 處理
但這會令代碼變得噁心