Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 6728 Accepted
Submission(s): 2556
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 9 struct node 10 { 11 int x,y; 12 }; 13 node a[102],stack1[102]; 14 15 double dis(node n1,node n2)//求距离 16 { 17 return (double)sqrt( (n1.x-n2.x)*(n1.x-n2.x)*1.0 + (n1.y-n2.y)*(n1.y-n2.y)*1.0 ); 18 } 19 double cross(node a,node n1,node n2)// 为正时 "左转" 20 { 21 return (n1.x-a.x)*(n2.y-a.y) - (n1.y-a.y)*(n2.x-a.x); 22 } 23 bool cmp(node n1,node n2)// 叉乘越小的,越靠前 24 { 25 double k = cross(a[0],n1,n2); 26 if( k>0) return true; 27 else if( k==0 && dis(a[0],n1)<dis(a[0],n2)) 28 return true; 29 else return false; 30 } 31 void Graham(int n) 32 { 33 int i,head; 34 double r=0; 35 for(i=1;i<n;i++) 36 if(a[i].x<a[0].x ||(a[i].x==a[0].x&&a[i].y<a[0].y ) ) 37 swap(a[0],a[i]); 38 sort(a+1,a+n,cmp); //排序 39 a[n]=a[0]; //为了形成园,把最初的再填到最后。 40 stack1[0]=a[0]; 41 stack1[1]=a[1]; 42 stack1[2]=a[2];// 放入3个先 43 head=2; 44 for(i=3;i<=n;i++) 45 { 46 while( head>=2 && cross(stack1[head-1],stack1[head],a[i])<=0 )head--; 47 // ==0 去除了坐标相等的。知道满足 左转。 48 stack1[++head]=a[i]; 49 } 50 for(i=0;i<head;i++) //不要<=,因为已经把a[0]放到最后了。 51 { 52 r=r+dis(stack1[i],stack1[i+1]); 53 } 54 printf("%.2lf\n",r); 55 } 56 int main() 57 { 58 int i,n; 59 while(scanf("%d",&n)>0) 60 { 61 if(n==0)break; 62 for(i=0;i<n;i++) 63 scanf("%d%d",&a[i].x,&a[i].y);//end input 64 if(n==1)//特判 65 { 66 printf("0.00\n"); 67 continue; 68 } 69 if(n==2)//此题的特判 70 { 71 printf("%.2lf\n",dis(a[0],a[1])); 72 continue; 73 } 74 Graham(n); 75 } 76 return 0; 77 }
hdu 1392 Surround the Trees 凸包模板,布布扣,bubuko.com
hdu 1392 Surround the Trees 凸包模板
原文:http://www.cnblogs.com/tom987690183/p/3577254.html