Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 28112 | Accepted: 9383 |
Description
Input
Output
Sample Input
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
Sample Output
1628
Hint
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 const double pi = acos(-1.0); 9 10 struct node 11 { 12 int x,y; 13 }; 14 node a[1002],stack1[1002]; 15 16 double dis(node n1,node n2) 17 { 18 return (double)sqrt( (n1.x-n2.x)*(n1.x-n2.x)*1.0 + (n1.y-n2.y)*(n1.y-n2.y)*1.0 ); 19 } 20 double cross(node a,node n1,node n2) 21 { 22 return (n1.x-a.x)*(n2.y-a.y) - (n1.y-a.y)*(n2.x-a.x); 23 } 24 bool cmp(node n1,node n2) 25 { 26 double k = cross(a[0],n1,n2); 27 if( k>0) return true; 28 else if( k==0 && dis(a[0],n1)<dis(a[0],n2)) 29 return true; 30 else return false; 31 } 32 double Graham(int n) 33 { 34 int i,head; 35 double r=0; 36 for(i=1;i<n;i++) 37 if(a[i].x<a[0].x ||(a[i].x==a[0].x&&a[i].y<a[0].y ) ) 38 swap(a[0],a[i]); 39 sort(a+1,a+n,cmp); 40 a[n]=a[0]; 41 stack1[0]=a[0]; 42 stack1[1]=a[1]; 43 stack1[2]=a[2]; 44 head=2; 45 for(i=3;i<=n;i++) 46 { 47 while( head>=2 && cross(stack1[head-1],stack1[head],a[i])<=0 )head--; 48 stack1[++head]=a[i]; 49 } 50 for(i=0;i<head;i++) 51 { 52 r=r+dis(stack1[i],stack1[i+1]); 53 } 54 return r; 55 } 56 int main() 57 { 58 int n,L,i; 59 double ans; 60 while(scanf("%d%d",&n,&L)>0) 61 { 62 for(i=0;i<n;i++) 63 scanf("%d%d",&a[i].x,&a[i].y); 64 ans=Graham(n); 65 ans=ans+2*pi*L; 66 printf("%.0lf\n",ans); 67 } 68 return 0; 69 }
poj 1113 Wall 凸包,布布扣,bubuko.com
原文:http://www.cnblogs.com/tom987690183/p/3578928.html