刷一发凸包模板。
这个题， 我们可以发现， 凹进去的是没有用的... 所以答案就是点构成的凸包的周长+一个圆的周长。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; const int maxn = 1005; struct point { int x,y; }; point a[maxn]; int st[maxn], top; int cross(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } double dis(point p1,point p2) { return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); } bool cmp(point p1,point p2) { int tmp=cross(a[0],p1,p2); if(tmp>0) return true; else if(tmp==0&&dis(a[0],p1)<dis(a[0],p2)) return true; else return false; } void init(int n) { int i,k; point p0; scanf("%d%d",&a[0].x,&a[0].y); p0.x=a[0].x; p0.y=a[0].y; k=0; for(i=1;i<n;i++) { scanf("%d%d",&a[i].x,&a[i].y); if( (p0.y>a[i].y) || ((p0.y==a[i].y)&&(p0.x>a[i].x)) ) { p0.x=a[i].x; p0.y=a[i].y; k=i; } } a[k]=a[0]; a[0]=p0; sort(a+1,a+n,cmp); } void graham(int n) { int i; if(n==1) {top=0;st[0]=0;} if(n==2) { top=1; st[0]=0; st[1]=1; } if(n>2) { for(i=0;i<=1;i++) st[i]=i; top=1; for(i=2;i<n;i++) { while(top>0&&cross(a[st[top-1]],a[st[top]],a[i])<=0) top--; top++; st[top]=i; } } } int main() { int n, r; while(cin>>n>>r) { init(n); graham(n); double ans = 0; for(int i = 0; i<top; i++) { ans += dis(a[st[i]], a[st[i+1]]); } ans += dis(a[st[top]], a[st[0]]); ans += 2*PI*r; cout<<(int)(ans+0.5)<<endl; } return 0; }