Surround the Trees

  1 /******************************  2 code by drizzle  3 blog: www.cnblogs.com/hsd-/  4 ^ ^    ^ ^  5  O      O  6 ******************************/  7 #include<bits/stdc++.h>  8 #include<map>  9 #include<set> 10 #include<cmath> 11 #include<queue> 12 #include<bitset> 13 #include<math.h> 14 #include<vector> 15 #include<string> 16 #include<stdio.h> 17 #include<cstring> 18 #include<iostream> 19 #include<algorithm> 20 #pragma comment(linker, "/STACK:102400000,102400000") 21 using namespace std; 22 #define  A first 23 #define B second 24 const int mod=1000000007; 25 const int MOD1=1000000007; 26 const int MOD2=1000000009; 27 const double EPS=0.00000001; 28 typedef __int64 ll; 29 const ll MOD=1000000007; 30 const int INF=1000000010; 31 const ll MAX=1ll<<55; 32 const double eps=1e-8; 33 const double inf=~0u>>1; 34 const double pi=acos(-1.0); 35 typedef double db; 36 typedef unsigned int uint; 37 typedef unsigned long long ull; 38 struct point 39 { 40     double x,y; 41     point(double x=0,double y=0):x(x),y(y) {} 42 }; 43 typedef point vec; 44 vec operator -(point a,point b) 45 { 46     return vec(a.x-b.x,a.y-b.y); 47 } 48 vec operator +(point a,point b) 49 { 50     return vec(a.x+b.x,a.y+b.y); 51 } 52 vec operator *(point a,double t) 53 { 54     return vec(a.x*t,a.y*t); 55 } 56 vec operator /(point a,double t) 57 { 58     return vec(a.x/t,a.y/t); 59 } 60 int dcmp(double x) 61 { 62     if(fabs(x)<=eps) return 0; 63     return x<0?-1:1; 64 } 65 double cross(vec a,vec b)  ///叉积 66 { 67     return a.x*b.y-a.y*b.x; 68 } 69 bool cmp(point a,point b) 70 { 71     if(fabs(a.x-b.x)<=eps) return a.y<b.y; 72     return a.x<b.x; 73 } 74 double disn(point a,point b) 75 { 76     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 77     /*两点之间的距离*/ 78 } 79 void convexhull(point *s,int &n) 80 { 81     sort(s,s+n,cmp); 82     int m=0; 83     point p[110]; 84     for(int i=0; i<n; i++) 85     { 86         while(m>1 && dcmp(cross(p[m-1]-p[m-2],s[i]-p[m-2]))<=0) 87             m--; 88         p[m++]=s[i]; 89     } 90     int k=m; 91     for(int i=n-2; i>=0; i--) 92     { 93         while(m>k && dcmp(cross(p[m-1]-p[m-2],s[i]-p[m-2]))<=0) 94             m--; 95         p[m++]=s[i]; 96     } 97     m--; 98     n=m; 99     for(int i=0; i<n; i++) s[i]=p[i];100     /*建立凸包*/101 }102 int jishu;103 int main()104 {105     while(scanf("%d",&jishu)!=EOF)106     {107         if(jishu==0)108             break;109         point s[110];110         for(int i=0; i<jishu; i++)111         {112             scanf("%lf %lf",&s[i].x,&s[i].y);113 114         }115         if(jishu==1)116         {117             printf("0.00\n");118                 continue;119         }120         if(jishu==2)121         {122             printf("%.2f\n",disn(s[0],s[1]));123                continue;124         }125         convexhull(s,jishu);126         double sum=0;127         for(int i=0; i<jishu-1; i++)128         {129             sum+=disn(s[i],s[i+1]);130         }131         sum+=disn(s[jishu-1],s[0]);132         printf("%.2f\n",sum);133     }134     return 0;135 }