UVa 1303 - Wall
栏目：互联网时间：2014-09-23 12:10:00
题目：有很多点，修一座最短的围墙把素有点围起来，使得所有点到墙的距离不小于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(
------分隔线----------------------------
------分隔线----------------------------