这个题要自己亲手画一画图,举个例子在纸上画一画,例如正方形,你会发现题目要求的是凸包的周长+圆的周长,下面是我的CODE,作为笔记。
1/**//*
2 Name: pku1113
3 Copyright: ccnu
4 Author:Torres
5 Date: 11-08-08 12:04
6 Description: 凸包
7*/
8#include<iostream>
9#include<cmath>
10#include<algorithm>
11using namespace std;
12const double pi=acos(-1.0);
13typedef struct point{
14 double x,y;
15 point(double x=0,double y=0)
16 {this->x=x;this->y=y;}
17}point;
18int n,r;
19point p[1005],ch[1005];
20int top;
21
22//p0p1 crossmul p0p2
23double cross(point p0,point p1,point p2)
24{return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}
25
26double dist(point a,point b)
27{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
28
29double area(point a,point b)
30{return fabs(a.x*b.y-a.y*b.x);}
31
32bool cmp(point a,point b)
33{
34 double re=cross(p[0],a,b);
35 if(re>0)return true;
36 else if(!re&&dist(p[0],a)>dist(p[0],b))
37 return true;
38 else return false;
39}
40
41int main()
42{
43 int i,j;
44 double sum=0;
45 scanf("%d%d",&n,&r);
46 for(i=0;i<n;i++)
47 scanf("%lf%lf",&p[i].x,&p[i].y);
48 j=0;
49 for(i=1;i<n;i++)
50 if(p[i].y<p[j].y||p[i].y==p[j].y&&p[i].x<p[j].x)
51 j=i;
52 swap(p[0],p[j]);
53 sort(p+1,p+n,cmp);
54 ch[0]=p[0];ch[1]=p[1];ch[2]=p[2];top=2;
55 for(i=3;i<n;i++){
56 while(cross(ch[top-1],p[i],ch[top])>=0)
57 {
58 top--;
59 if(top==1)break;
60 }
61 ch[++top]=p[i];
62 }
63 for(i=0;i<
64 top;i++)
65 sum+=sqrt(dist(ch[i],ch[i+1]));
66 sum+=2*pi*r+sqrt(dist(ch[top],ch[0]));
67 printf("%.0lf\n",sum);
68 return 0;
69}
70