题目地址：POJ 1113
先求出凸包的周长，然后剩下的弧合起来一定是个半径为l的圆，然后再加上以l为半径的圆的周长即可。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const int INF=0x3f3f3f3f; int n, top, l; double PI=acos(-1.0); struct Point { int x, y; }p[1010], tu[1010]; double dist(Point x, Point y) { return sqrt((x.x-y.x)*(x.x-y.x)*1.0+(x.y-y.y)*(x.y-y.y)); } Point operator - (Point x, Point y) { Point z; z.x=x.x-y.x; z.y=x.y-y.y; return z; } int Cross(Point x, Point y) { return x.x*y.y-x.y*y.x; } int cmp(Point x, Point y) { if(x.x==y.x) return x.y 1&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<0) top--; tu[top++]=p[i]; } k=top; for(i=n-2;i>=0;i--) { while(top>k&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<0) top--; tu[top++]=p[i]; } double ans=0; for(i=1;i