USACO Section 5.1 Fencing the Cows - 凸包模板题~~

USACO本节开头的TXT将得就是凸包的求法~~

题目的原意是给出N个点...问最少要用多长的栅栏才能将所有点都围起来..

求出平面中这些点的凸包...凸包的周长就是解..很好想到的..

我是用Graham写的...好久没写凸包了...很不熟练...调了一晚上才出来...再次总结一下Graham求凸包的顺序:

1 . 找出最左下方的点...并将其挪到point [ 0 ] 方便操作...

2 . 以这个点为原点求出其他所有点的极角,并按极角对除左下方的所有点重新排序..( 开始我想当极角相等时需不需要按到左下点的距离进行二次判断,发现没有必要..只要按极角排序就可以了 )

3 . 可以肯定地是极角最大的点和最小的点肯定在凸包上..用一个栈..将重新排序后的0,1先依次压入栈...

4 . 从point [ 2 ] 开始扫到 point [ n ] 每次的目的是将这个点加到凸包上..若加不上去 ( 非向左拐 )..就弹栈,直到加上这个点是向左拐的...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: fc */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node1 { double x,y,alp; }point[10005]; double dist(node1 a,node1 b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool cmp(node1 a,node1 b) { return a.alp<b.alp; } int n,k; bool left(node1 a,node1 b,node1 c) { double x1,y1,x2,y2; x1=b.x-a.x; y1=b.y-a.y; x2=c.x-a.x; y2=c.y-a.y; if (x1*y2-x2*y1>-0.00001) return true; return false; } double Graham() { int i,num,mystack[10005]; double ans=0; num=2; mystack[1]=0; mystack[2]=1; for (i=2;i<=n;i++) { while (!left(point[mystack[num-1]],point[mystack[num]],point[i])) num--; mystack[++num]=i; } mystack[num+1]=0; for (i=1;i<=num;i++) ans+=dist(point[mystack[i]],point[mystack[i+1]]); return ans; } int main() { freopen("fc.in","r",stdin); freopen("fc.out","w",stdout); int i; scanf("%d",&n); k=1; for (i=1;i<=n;i++) { scanf("%lf%lf",&point[i].x,&point[i].y); if (point[i].x<point[k].x) k=i; else if (absb(point[i].x-point[k].x)<0.00001 && point[i].y<point[k].y) k=i; } point[0]=point[k]; point[k]=point[n]; n--; for (i=1;i<=n;i++) point[i].alp=(point[i].y-point[0].y)/dist(point[i],point[0]); sort(point+1,point+1+n,cmp); printf("%.2lf\n",Graham()); return 0; }