题目:http://poj.org/problem?id=1113
题意:给定多边形城堡的n个顶点,绕城堡外面建一个围墙,围住所有点,并且墙与所有点的距离至少为L,求这个墙最小的长度。
公式:
城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长
View Code
1 #include2 #include 3 #include 4 #include 5 #define PI 3.1415926535 6 using namespace std; 7 const double eps=1e-6; 8 typedef struct node 9 {10 int x,y;11 }point;12 int n;13 point pt[1100];14 point res[1100];15 bool cmp(point a,point b)16 {17 if(a.x==b.x)18 return a.y 1&&cross(res[m-1],pt[i],res[m-2])<=0)58 m--;59 res[m++]=pt[i];60 }61 int k=m;62 for(i=n-2;i>=0;i--)63 {64 while(m>k&&cross(res[m-1],pt[i],res[m-2])<=0)65 m--;66 res[m++]=pt[i];67 }68 if(n>1)69 m--;70 double dis=0;71 for(i=0;i