UVa 1303 - Wall

題目：有很多點，修一座最短的圍墻把素有點圍起來，使得所有點到墻的距離不小于l。

分析：計算幾何，凸包。

            如果，沒有距離l的限制，則答案就是凸包的周長了；有了距離限制其實是增加了2*π*l；

            證明：如上圖，在凸包外做對應邊的矩形；

                        多邊形內角和 = 180*（n-2）；

                        外角和 = 360*n - 內角和 = 180*n+360；

                        所有直角和為2*90*n；

                        所以，所有扇形的內角和為360；即圍欄比凸多邊形周長多2*π*l。

說明：坐標比較a3.x < b.x 寫成 a.x < b.y 查了好久才發現，o(

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈