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;     
}