Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 2848 Accepted
Submission(s): 811
7 - 8 - 9 - 1 - 2 - 5 - 6 - 7
最后一个点回到起点，这就构成了一个凸包。
思路详见：
http://dev.gameres.com/Program/Abstract/Geometry.htm#凸包的求法
之后根据两点间的距离公式求出凸包周长，这道题还要再加上国王周围一个圆的周长（圆半径为L）。
注意输出不需要浮点部分，直接控制输出浮点数位数为0。
自己写的模板（求凸包周长）：
1 struct Point{
2 double x,y;
3 };
4 double dis(Point p1,Point p2)
5 {
6 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
7 }
8 double xmulti(Point p1,Point p2,Point p0) //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向
9 {
10 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
11 }
12 double graham(Point p[],int n) //点集和点的个数
13 {
14 int pl[10005];
15 //找到纵坐标（y）最小的那个点，作第一个点
16 int t = 1;
17 for(int i=1;i<=n;i++)
18 if(p[i].y < p[t].y)
19 t = i;
20 pl[1] = t;
21 //顺时针找到凸包点的顺序，记录在 int pl[]
22 int num = 1; //凸包点的数量
23 do{ //已确定凸包上num个点
24 num++; //该确定第 num+1 个点了
25 t = pl[num-1]+1;
26 if(t>n) t = 1;
27 for(int i=1;i<=n;i++){ //核心代码。根据叉积确定凸包下一个点。
28 double x = xmulti(p[i],p[t],p[pl[num-1]]);
29 if(x<0) t = i;
30 }
31 pl[num] = t;
32 } while(pl[num]!=pl[1]);
33 //计算凸包周长
34 double sum = 0;
35 for(int i=1;i<num;i++)
36 sum += dis(p[pl[i]],p[pl[i+1]]);
37 return sum;
38 }
本题代码：
1 #include <iostream>
2 #include <cmath>
3 #include <iomanip>
4 using namespace std;
5 struct Point{
6 double x,y;
7 };
8 double dis(Point p1,Point p2)
9 {
10 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
11 }
12 double xmulti(Point p1,Point p2,Point p0) //求p1p0和p2p0的叉积,如果大于0,则p1在p2的顺时针方向
13 {
14 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
15 }
16 double graham(Point p[],int n) //点集和点的个数
17 {
18 int pl[10005];
19 //找到纵坐标（y）最小的那个点，作第一个点
20 int t = 1;
21 for(int i=1;i<=n;i++)
22 if(p[i].y < p[t].y)
23 t = i;
24 pl[1] = t;
25 //顺时针找到凸包点的顺序，记录在 int pl[]
26 int num = 1; //凸包点的数量
27 do{ //已确定凸包上num个点
28 num++; //该确定第 num+1 个点了
29 t = pl[num-1]+1;
30 if(t>n) t = 1;
31 for(int i=1;i<=n;i++){ //核心代码。根据叉积确定凸包下一个点。
32 double x = xmulti(p[i],p[t],p[pl[num-1]]);
33 if(x<0) t = i;
34 }
35 pl[num] = t;
36 } while(pl[num]!=pl[1]);
37 //计算凸包周长
38 double sum = 0;
39 for(int i=1;i<num;i++)
40 sum += dis(p[pl[i]],p[pl[i+1]]);
41 return sum;
42 }
43 const double PI = 3.1415927;
44 int main()
45 {
46 int T,N;
47 double L;
48 Point p[1005];
49 cin>>T;
50 cout<<setiosflags(ios::fixed)<<setprecision(0);
51 while(T--){
52 cin>>N>>L;
53 for(int i=1;i<=N;i++)
54 cin>>p[i].x>>p[i].y;
55 cout<<graham(p,N)+2*PI*L<<endl;
56 if(T)
57 cout<<endl;
58 }
59 return 0;
60 }
Freecode : www.cnblogs.com/yym2013
原文：http://www.cnblogs.com/yym2013/p/3540991.html