Graham

今天照着自己的理解写了Graham.
自己写错了很多次，所以先前看到的可能错了。。
View Code
 1 const int maxn = 105;
 2 struct Point
 3 {
 4     float x,y;
 5 }p[maxn],stack[maxn];
 6 
 7 double xmult(Point p1,Point p2,Point p0)        //cross product 
 8 {
 9     return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
10 }
11 
12 double dis(Point p1,Point p2)        //distance
13 {
14     return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
15 }
16 
17 bool cmp(Point a,Point b)    //sort the element of the point besides p[0]
18 {
19     double has;
20     has=xmult(a,b,p[0]);
21     if(has>0)        // a is the right of the b
22         return 1;
23     else if((has==0)&& (dis(a,p[0])<dis(b,p[0])))        //sort by distance
24         return 1;
25     else
26         return 0;        //a is the left of th b
27 }
28 
29 void swap(int r,int s)      
30 {
31     Point temp;
32     temp=p[r];
33     p[r]=p[s];
34     p[s]=temp;
35 }
36 
37 //Graham
38 int Graham(int n)
39 {
40     int i,top,k;
41     Point ans;
42     top=2;
43     if(n<=3)        
44     {
45         for(i=0;i<n;i++)
46             stack[i]=p[i];
47         return n;
48     }
49     k=0;
50     for(i=1;i<n;i++)        //find the left-under point
51     if((p[i].y<p[k].y )|| ((p[i].y==p[k].y)&&(p[i].x<p[k].x)))
52         k=i;
53     ans=p[0];    p[0]=p[k];    p[k]=ans;        //set the left-under to the p[0]
54     sort(p+1,p+n,cmp);    
55     for(i=0;i<=top;i++)
56         stack[i]=p[i];
57     for(i=top+1;i<n;i++)
58     {
59         if((i+1<n)&&(xmult(p[i],p[i+1],p[0])==0))        //the point in a line
60             continue;
61         while(xmult(p[i],stack[top],stack[top-1])>=0)        //if the p[i] is the right of the stack[top]
62                     top--;                                        //choose the p[i]
63         stack[++top]=p[i];    
64     }
65     return ++top;
66 }