大家好,又见面了,我是全栈君。
Surround the Trees
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7203 Accepted Submission(s): 2752
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.
There are no more than 100 trees.
Zero at line for number of trees terminates the input for your program.
9 12 7 24 9 30 5 41 9 80 7 50 87 22 9 45 1 50 7 0
243.06
水平序的Andrew算法:
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct node { double x,y; }a[105],b[105]; double cmp(node n,node m) //先比較X坐标,在比較Y坐标(从小到大) { if(n.x != m.x) return n.x < m.x; else return n.y < m.y; } double Cross(node a,node b,node c) //计算叉积大小 { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } double dis(node a,node b) //计算距离 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int CH(node* a,int n,node* b) { sort(a,a+n,cmp); int m=0,i; for(i=0;i<n;i++) //从左往右,选下边界 { while(m > 1 && Cross(b[m-2],b[m-1],a[i]) < 0) m--; b[m++]=a[i]; } int k=m; for(i=n-2;i>=0;i--) //从右往左,选上边界 { while(m > k && Cross(b[m-2],b[m-1],a[i]) < 0) m--; b[m++]=a[i]; } if(n >1) m--; return m; } int main() { int n; while(cin>>n) { if(n==0) break; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int i,j; for(i=0;i<n;i++) { cin>>a[i].x>>a[i].y; } // cout<<CH(a,n,b)<<endl; //输出所选点的总数 if(n==1) cout<<0.00<<endl; else if(n==2) printf("%.2lf\n",dis(a[0],a[1])); else { int m=CH(a,n,b); double s=0; for(i=1;i<m;i++) s+=dis(b[i-1],b[i]); s+=dis(b[0],b[m-1]); printf("%.2lf\n",s); } // for(i=0;i<CH(a,n,b);i++) //输出所选点的坐标 // cout<<b[i].x<<" "<<b[i].y<<endl; } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115357.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...