Surround the Trees

  1 //求凸包的模板题Graham扫描法。
  2 //详解《算法导论》604页
  3 //极角排序先比较象限再比较叉积。
  4 #include<iostream>
  5 #include<cstdio>
  6 #include<cstring>
  7 #include<algorithm>
  8 #include<cmath>
  9 using namespace std;
 10 int top,n;
 11 struct nod
 12 {
 13     double x,y;
 14 } p[102],que[102];  //que用于保存组成凸包的点
 15 int xy(nod p0)   //返回点相对于p[0]点所在的象限
 16 {
 17     p0.x-=p[0].x;
 18     p0.y-=p[0].y;
 19     if(p0.x>=0&&p0.y>=0) return 1;
 20     if(p0.x<=0&&p0.y>0) return 2;
 21     if(p0.x<0&&p0.y<=0) return 3;
 22     if(p0.x>=0&&p0.y<0) return 4;
 23 }
 24 double dis(nod p1,nod p2)    //计算凸包边长
 25 {
 26     return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
 27 }
 28 double chaji(nod p0,nod p1,nod p2)  //叉积
 29 {
 30     return ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
 31 }
 32 bool cmp(nod p1,nod p2)
 33 {
 34     int L1=xy(p1),L2=xy(p2);
 35     if(L1==L2)
 36     {
 37         int tem=chaji(p[0],p1,p2);
 38         if(tem>0) return 1;   //tem>0说明向量p1p0在向量p2p0的顺时针方向即p1p0相对于p0的极角小于p2p0的
 39         if(tem<0) return 0;
 40         if(tem==0)
 41             return p1.x<p2.x;
 42     }
 43     else return L1<L2;
 44 }
 45 void tubao()
 46 {
 47     top=0;
 48     que[top].x=p[0].x;
 49     que[top++].y=p[0].y;
 50     que[top].x=p[1].x;
 51     que[top++].y=p[1].y;
 52     que[top].x=p[2].x;
 53     que[top].y=p[2].y;
 54     for(int i=3; i<=n; i++)
 55     {
 56         while(chaji(que[top-1],que[top],p[i])<=0)
 57             top--;
 58         que[++top].x=p[i].x;
 59         que[top].y=p[i].y;
 60     }
 61 }
 62 int main()
 63 {
 64     while(scanf("%d",&n)&&n)
 65     {
 66         int Miny=10000007,Minx=10000007,Mini;
 67         for(int i=0; i<n; i++)
 68         {
 69             scanf("%lf%lf",&p[i].x,&p[i].y);
 70             if(p[i].y<Miny)
 71             {
 72                 Miny=p[i].y;
 73                 Mini=i;
 74             }
 75             else if(p[i].y==Miny&&p[i].x<Minx)
 76             {
 77                 Minx=p[i].x;
 78                 Mini=i;
 79             }
 80         }
 81         if(n==1) {printf("0.00\n");continue;}
 82         if(n==2) {printf("%.2lf\n",dis(p[0],p[1]));continue;}  //计算凸包的点数必须多于2
 83         int tem=p[0].x;
 84         p[0].x=p[Mini].x;
 85         p[Mini].x=tem;
 86         tem=p[0].y;
 87         p[0].y=p[Mini].y;
 88         p[Mini].y=tem;
 89         sort(p+1,p+n,cmp);
 90         p[n].x=p[0].x;p[n].y=p[0].y; //形成闭合的凸包
 91         tubao();
 92         double ans=0.0;
 93         for(int i=0;i<top;i++)
 94         {
 95             ans+=dis(que[i],que[i+1]);
 96         }
 97         printf("%.2lf\n",ans);
 98     }
 99     return 0;
100 }