POJ 1113

求凸包....

完全上模板的，先过了，然后自己在仔细看看Graham算法

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <math.h>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn =1005;
 7 const float pi = 3.14159265;
 8 struct Point
 9 {
10     float x,y;
11 }p[maxn],ch[maxn];
12 
13 double xmult(Point p1,Point p2,Point p0){
14     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
15 }
16 double dis(Point p, Point q){
17     return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
18 }
19 int cmp(Point a,Point b){
20     float mu=xmult(a,b,p[0]);
21     if(mu>0) return 1;
22     if((mu==0)&&(dis(p[0],a)<dis(p[0],b))) return 1;
23     return 0;
24 }
25 int Graham(int n){
26     int i,top,k;
27     Point tmp;
28     k=0; top=2;
29     if(n<=3){
30         for(i=0;i<4;i++) ch[i]=p[i];
31         return n;
32     }
33     for(i=1;i<n;i++)
34         if((p[i].y<p[k].y)||((p[i].y==p[k].y)&&(p[i].x>p[k].x))) k=i;
35     tmp=p[0]; p[0]=p[k]; p[k]=tmp;
36     sort(p+1,p+n,cmp);
37     ch[0]=p[0]; ch[1]=p[1]; ch[2]=p[2];
38     for(i=3;i<n;i++){
39         if((i+1<n)&&(xmult(p[i],p[i+1],p[0])==0)) 
40             continue;
41         while(xmult(p[i],ch[top],ch[top-1])>=0) top--;
42         ch[++top]=p[i];
43     }
44     return ++top;
45 }
46 
47 int main()
48 {
49     int n,l,i,top;
50     double num;
51     scanf("%d%d",&n,&l);
52     for(i=0;i<n;i++)
53         scanf("%f%f",&p[i].x,&p[i].y);    
54     top=Graham(n);
55     num=0;
56     for(i=0;i<top;i++)
57     {
58         num+=sqrt(dis(ch[i%top],ch[(i+1)%top]));
59     }
60     num+=2*pi*l;
61     if(num-(int)num >= 0.5)
62         printf("%d\n",(int)num+1);
63     else
64         printf("%d\n",(int)num);
65     return 0;
66 }

本来一直错，因为原来的模板是qsort，被我改成了sort。

然后在sort()中写错了长度，还有自己对Graham中的一些步骤刚开始的时候有些不了解....

刚开始的时候以为当共线时只计算一次，且将共线的距离按照从大到小的排列。

实际上共线时，距离是从小到大，然后是不计算前面的，只有在最后一个不是共线的点的时候才将这个点放入点集中。