poj 1113Walls解题报告

求凸包的模板题，只是这个精度卡死人，而且我的g++死活过不了，换成c++就过了，唉，poj上太多这样的题了，实在让人无语啊

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 #define N 1005
 5 #define pi 3.141592653
 6 struct point
 7 {
 8     int x,y;
 9 };
10 int n;
11 int dis(point p1,point p2)
12 {
13     return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
14 }
15 point p[N],res[N];
16 int mul(point p1,point p2,point p3)
17 {
18     return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
19 }
20 int cmp(const void *a,const void *b)//极角排序，要注意快速排序的排序函数
21 {
22     point c=*(point *)a;
23     point d=*(point *)b;
24     int t=mul(p[0],c,d);
25     if(t)
26     return -t;
27     return dis(p[0],d)-dis(p[0],c);
28 }
29 int graham()
30 {
31     int i,j,k,top=2;
32     j=0;
33     for(i=1;i<n;i++)
34     {
35         if(p[i].y<p[j].y||(p[i].y==p[j].y&&p[i].x<p[j].x))
36         j=i;
37     }
38     if(j)
39     {
40         point temp=p[j];
41         p[j]=p[0];
42         p[0]=temp;
43     }
44     qsort(p+1,n-1,sizeof(p[0]),cmp);
45     //for(i=0;i<n;i++)
46     //printf("%d %d\n",p[i].x,p[i].y);
47     res[0]=p[0];
48     res[1]=p[1];
49     res[2]=p[2];
50     for(i=3;i<n;i++)
51     {
52         while(top>1&&mul(res[top-1],res[top],p[i])<=0)
53         --top;
54         res[++top]=p[i];
55     }
56     return top;
57 }
58 int main()
59 {
60     int i,j,k;
61     int l;
62     while(scanf("%d%d",&n,&l)!=EOF)
63     {
64         for(i=0;i<n;i++)
65         scanf("%d%d",&p[i].x,&p[i].y);
66         int t=graham();
67         res[t+1]=res[0];
68         //for(i=0;i<=t+1;i++)
69         //printf("%.lf %.lf\n",res[i].x,res[i].y);
70         double ans=0;
71         for(i=0;i<=t;i++)
72         ans+=sqrt((double)dis(res[i],res[i+1]));
73         ans+=2*pi*l;
74         printf("%.lf\n",ans);
75     }
76     return 0;
77 }