USACO Fencing the Cows

直接的求凸包题。USACO的TEXT中介绍的是gift-wrapping方法。本人推荐用Graham扫描法，在《算法导论》和维基百科上都有详细介绍。Graham扫描是一种相当直观的算法，代码也很短小，《算法导论》里有Graham扫描法证明。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #include <math.h>
005
006 typedef struct node
007 {
008     double x,y;
009     double dist,angle;
010 }POINT;
011
012
013 POINT p[10000] = {};
014 int n;
015
016 void init()
017 {
018     scanf("%d\n",&n);
019     int i,minp;
020     double minx,miny;
021     minx = miny = 10000000;
022     for(i = 0;i < n;i ++)
023     {
024         scanf("%lf%lf",&p[i].x,&p[i].y);
025         if(p[i].y < miny)
026         {
027             minx = p[i].x;
028             miny = p[i].y;
029             minp = i;
030         }
031         else if((p[i].y == miny) && (p[i].x < minx))
032         {
033             minx = p[i].x;
034             miny = p[i].y;
035             minp = i;
036         }
037     }
038     p[minp].x = p[0].x;
039     p[minp].y = p[0].y;
040     p[0].x = minx;
041     p[0].y = miny;
042 }
043
044 double dist(double x1,double y1,double x2,double y2)
045 {
046     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
047 }
048
049 double cp(POINT a, POINT b, POINT c)
050 {
051     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
052 }
053
054 int stack[10000];
055 int top = 0;
056
057 void push(int x)
058 {
059     stack[top ++] = x;
060 }
061
062 int get_top()
063 {
064     return stack[top - 1];
065 }
066
067 int get_next_top()
068 {
069     return stack[top - 2];
070 }
071
072 int cmp(const void *a,const void *b)
073 {
074     if((((struct node *)a)->angle) < (((struct node *)b)->angle))    return 1;
075     if((((struct node *)a)->angle) == (((struct node *)b)->angle) && ((struct node *)a)->dist < ((struct node *)b)->dist)    return 1;
076     return 0;
077 }
078
079 void angle_sort()
080 {
081     int i;
082     for(i = 1;i < n;i ++)
083     {
084         p[i].dist = dist(p[0].x, p[0].y, p[i].x, p[i].y);
085         p[i].angle = (p[i].x - p[0].x) / p[i].dist;
086     }
087     qsort(p + 1,n - 1,sizeof(struct node),cmp);
088     /*for(i = 0;i < n;i ++)
089         fprintf(stderr,"%.2lf %.2lf %lf\n",p[i].x,p[i].y,p[i].angle);*/
090 }
091
092 void scan()
093 {
094     int a,b;
095     int i;
096     push(0);push(1);push(2);
097     for(i = 3;i < n;i ++)
098     {
099         a = get_next_top();
100         b = get_top();
101         while(cp(p[a],p[b],p[i]) < 0 && top > 2)
102         {
103             top --;
104             a = get_next_top();
105             b = get_top();
106         }
107         push(i);
108     }
109 }
110
111 void circ()
112 {
113     double c = 0;
114     int i;
115     for(i = 0;i < top - 1;i ++)
116         c += dist(p[stack[i]].x, p[stack[i]].y, p[stack[i + 1]].x, p[stack[i + 1]].y);
117     c += dist(p[stack[0]].x, p[stack[0]].y, p[stack[top - 1]].x, p[stack[top - 1]].y);
118     printf("%.2f\n",c);
119 }
120
121 int main()
122 {
123     freopen("fc.in","r",stdin);
124     freopen("fc.out","w",stdout);
125     init();
126     angle_sort();
127     scan();
128     circ();
129     return 0;
130 }