POJ1113

这是一道凸包的计算几何题。其实做法就是计算出凸包，然后再加上2πl，最后取整输出即可。至于为什么要加上2πl，我暂时还没想清楚。但在这里我想重点提一下Andrew算法。据刘汝佳《算法竞赛入门经典（训练指南）》所讲，该算法是Graham的改良，具有更快的速度和数值稳定性。其算法首先将点集按照x从小到大排序（若x相等，则按照y从小到大排序），然后分为两步：第一步将p1,p2放到凸包中，从p3开始，当新的点p3在向量p1p2的左边时继续，否则删除最近加入凸包的点，直到新点在左边，这样下去就可以得到“下凸包”；第二步从pn开始再做一次，求出“上凸包”就行了。

 1 #include <stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using std::sort;
 6 typedef struct
 7 {
 8     int x;
 9     int y;
10 }Point;
11 Point p[1001],ch[1001];
12 int n,l;
13 int Cross(const Point &A,const Point &B,const Point &C,const Point&D)
14 {
15     return (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);
16 }
17 double distant(Point A,Point B)
18 {
19     return sqrt((double)((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)));
20 }
21 bool cmp(const Point &A,const Point &B)//优先比较x,当x相同时比较y
22 {
23     if(A.x!=B.x)
24     return A.x<B.x;
25     return A.y<=B.y;
26 }
27 int ConvexHull(Point*p,int n,Point*ch)//Andrew算法，效率十分高，当做模版来用吧!
28 {
29     sort(p+1,p+n+1,cmp);
30     int m=0;
31     for(int i=1;i<=n;i++)
32     {
33         while(m>1&&Cross(ch[m-2],ch[m-1],ch[m-2],p[i])<=0)m--;
34         ch[m++]=p[i];
35     }
36     int k=m;
37     for (int i=n-1;i>=1;i--)
38     {
39         while(m>k&&Cross(ch[m-2],ch[m-1],ch[m-2],p[i])<=0)m--;
40         ch[m++]=p[i];
41     }
42     if(n>1)m--;
43     return m;
44 }
45 int main()
46 {
47     int i,j,k,min=655365,f;
48     double sum=0;
49     scanf("%d%d",&n,&l);
50     for(i=1;i<=n;i++)
51      scanf("%d%d",&p[i].x,&p[i].y);
52     f=ConvexHull(p,n,ch);
53     for(i=0;i<=f-2;i++)
54       sum+=distant(ch[i],ch[i+1]);
55     sum+=distant(ch[0],ch[f-1]);
56     sum+=(2*l*3.141592654);
57     printf("%.0lf\n",sum);
58     return 0;
59 }