首页 > 代码库 > hdu1392凸包裸题
hdu1392凸包裸题
1 //极角排序 2 #include <bits/stdc++.h> 3 #define sqr(x) ((x)*(x)) 4 using namespace std; 5 int n,st[200001],top; 6 struct POI 7 { 8 int x,y; 9 POI() 10 { 11 x=y=0; 12 } 13 POI(int _x,int _y) 14 { 15 x=_x;y=_y; 16 } 17 } p[200001]; 18 int cross(POI x,POI y) 19 { 20 return x.x*y.y-x.y*y.x; 21 } 22 double dis(POI x,POI y) 23 { 24 return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y)); 25 } 26 POI operator-(POI x,POI y) 27 { 28 return POI(x.x-y.x,x.y-y.y); 29 } 30 bool com(POI x,POI y) 31 { 32 return(cross(x-p[1],y-p[1])>0 || cross(x-p[1],y-p[1])==0 && dis(x,p[1])<dis(y,p[1])); 33 } 34 int main() 35 { 36 for(scanf("%d",&n);n;scanf("%d",&n)) 37 { 38 for(int i=1;i<=n;i++) 39 scanf("%d%d",&p[i].x,&p[i].y); 40 if(n==2)//wtf 41 { 42 printf("%.2f\n",dis(p[1],p[2])); 43 continue; 44 } 45 int id=1; 46 for(int i=2;i<=n;i++) 47 if(p[i].x<p[id].x || p[i].x==p[id].x && p[i].y<p[id].y) id=i; 48 swap(p[1],p[id]); 49 sort(p+2,p+n+1,com); 50 st[top=1]=st[0]=1; 51 for(int i=2;i<=n;i++) 52 { 53 while(top && cross(p[st[top]]-p[st[top-1]],p[i]-p[st[top]])<0) --top; 54 st[++top]=i; 55 } 56 double len=0; 57 // puts(""); 58 // for(int i=1;i<=top;i++) 59 // printf("%d %d\n",p[st[i]].x,p[st[i]].y); 60 st[++top]=1; 61 for(int i=1;i<top;i++) 62 len+=dis(p[st[i]],p[st[i+1]]); 63 printf("%.2f\n",len); 64 } 65 return 0; 66 }
hdu1392凸包裸题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。