首页 > 代码库 > 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 }
View Code

 

poj1113