就是求凸包的周长加以l为半径的圆周长，证明略
由于之前写过叉积，所以graham扫描算法不是很难理解
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=1000+10,maxn=500+100,inf=0x3f3f3f; struct point{ double x,y; }; point p[N],s[N]; int top,n; double dir(point p1,point p2,point p3) { return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x); } double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool comp(point a,point b) { int te=dir(p[0],a,b); if(te<0)return 1; if(te==0&&dis(p[0],a)<dis(p[0],b))return 1; return 0; } void graham() { int pos,minx,miny; minx=miny=inf; for(int i=0;i<n;i++) { if(p[i].x<minx||(p[i].x==minx&&p[i].y<miny)) { minx=p[i].x; miny=p[i].y; pos=i; } } swap(p[0],p[pos]); sort(p+1,p+n,comp); p[n]=p[0]; s[0]=p[0],s[1]=p[1],s[2]=p[2]; top=2; for(int i=3;i<=n;i++) { while(dir(s[top-1],s[top],p[i])>=0&&top>=2)top--; s[++top]=p[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int l; cin>>n>>l; for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y; graham(); double ans=2*pi*l; for(int i=0;i<top;i++) { // cout<<s[i].x<<" "<<s[i].y<<endl; if(i==top-1)ans+=dis(s[i],s[0]); else ans+=dis(s[i],s[i+1]); } cout<<(int)(ans+0.5)<<endl; return 0; } /* 4 3 0 0 1 0 0 1 1 1 */