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(

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠