首页 > 代码库 > poj1113
poj1113
http://poj.org/problem?id=1113
完全时copy大神给的模版哦,结果再加一个小圆的周长就好啦
1 #include<stdio.h> 2 #include<math.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 const double pi=acos(-1.0); 7 const int MAXN=1005; 8 9 struct point10 {11 int x,y;12 };13 point list[MAXN],list2[MAXN];14 int stack[MAXN],top;15 16 int cross(point p0,point p1,point p2) //计算叉积 p0p1 X p0p217 {18 return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);19 }20 double dis(point p1,point p2) //计算 p1p2的 距离21 {22 return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));23 }24 bool cmp(point p1,point p2) //极角排序函数 , 角度相同则距离小的在前面25 {26 int tmp=cross(list[0],p1,p2);27 if(tmp>0) return true;28 else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true;29 else return false;30 }31 void init(int n) //输入,并把 最左下方的点放在 list[0] 。并且进行极角排序32 {33 int i,k;34 point p0;35 scanf("%d%d",&list[0].x,&list[0].y);36 p0.x=list[0].x;37 p0.y=list[0].y;38 k=0;39 for(i=1;i<n;i++)40 {41 scanf("%d%d",&list[i].x,&list[i].y);42 if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) )43 {44 p0.x=list[i].x;45 p0.y=list[i].y;46 k=i;47 }48 }49 list[k]=list[0];50 list[0]=p0;51 52 sort(list+1,list+n,cmp);53 }54 55 void graham(int n)56 {57 int i;58 if(n==1) {top=0;stack[0]=0;}59 if(n==2)60 {61 top=1;62 stack[0]=0;63 stack[1]=1;64 }65 if(n>2)66 {67 for(i=0;i<=1;i++) stack[i]=i;68 top=1;69 70 for(i=2;i<n;i++)71 {72 while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<=0) top--;73 top++;74 stack[top]=i;75 }76 }77 }78 79 int main()80 {81 int m,n,r;82 point t;83 while(cin>>n){84 cin>>r;85 init(n);86 graham(n);87 double sum=0;88 for(int i=0;i<top;i++){89 90 sum+=dis(list[stack[i]],list[stack[i+1]]);///top的数值要弄清楚91 }92 93 sum+=dis(list[stack[0]],list[stack[top]]);94 sum=(int)(sum+2*pi*r+0.5);///四舍五入的精度95 printf("%.0f\n",sum);96 }97 }
poj1113
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。