题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1348
题意：让你求n个点的凸包，凸包离点的距离为l
题解：就凸包周长+一个半径为l的圆周长
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define F(i,a,b) for(int i=a;i<=b;++i) 5 using namespace std; 6 /* 7 * 求凸包，Graham算法 * 点的编号0~n-1 8 * 返回凸包结果Stack[0~top-1]为凸包的编号 9 */ 10 const int MAXN = 1010; 11 const double eps = 1e-8; 12 const double PI = acos(-1.0); 13 struct Point { 14 double x,y; 15 Point(){} 16 Point(double _x,double _y){x = _x,y = _y;} 17 Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);} 18 double operator ^(const Point &b)const{return x*b.y-y*b.x;}//叉积 19 double operator *(const Point &b)const{return x*b.x + y*b.y;}//点积 20 void transXY(double B){double tx = x,ty = y,x = tx*cos(B) - ty*sin(B),y = tx*sin(B) + ty*cos(B);} //绕原点旋转角度B（弧度值），后x,y的变化 21 }list[MAXN]; 22 int S[MAXN],top;//相对于list[0]的极角排序 23 int sgn(double x) { 24 if(fabs(x) < eps)return 0; 25 if(x < 0)return -1; 26 else return 1; 27 } 28 double dist(Point a,Point b){return sqrt((a-b)*(a-b));} 29 bool _cmp(Point p1,Point p2){ 30 double tmp =(p1-list[0])^(p2-list[0]); 31 if(sgn(tmp)>0)return 1; 32 else if(sgn(tmp)==0&&sgn(dist(p1,list[0])-dist(p2,list[0]))<= 0)return 1; 33 return 0; 34 } 35 void Graham(int n){ 36 Point p0=list[0],tp; 37 int k=0; 38 for(int i=1;i<n;i++)if((p0.y > list[i].y)||(p0.y ==list[i].y&&p0.x>list[i].x))p0 =list[i],k=i; 39 tp=list[k],list[k]=list[0],list[0]=tp,sort(list+1,list+n,_cmp); 40 if(n==1){top=1,S[0]=0;return;} 41 if(n==2){top=2,S[0]=0,S[1]=1;return;} 42 S[0]=0,S[1]=1,top=2; 43 for(int i=2;i<n;i++){ 44 while(top>1&&sgn((list[S[top-1]]-list[S[top-2]])^(list[i]-list[S[top-2]]))<=0)top--; 45 S[top++]=i; 46 } 47 } 48 49 int main(){ 50 int t,n,l; 51 scanf("%d",&t); 52 while(t--){ 53 scanf("%d%d",&n,&l); 54 F(i,0,n-1)scanf("%lf%lf",&list[i].x,&list[i].y); 55 Graham(n); 56 double ans=0; 57 F(i,0,top-2)ans+=dist(list[S[i]],list[S[i+1]]); 58 ans+=dist(list[S[0]],list[S[top-1]])+PI*2*l; 59 printf("%.0lf ",ans); 60 if(t!=0)puts(""); 61 } 62 return 0; 63 }