1 struct Point{
2 float x,y;
3 };
4
5 float multiply(Point p1,Point p2,Point p0)
6 {
7 return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
8 }
9
10 float distance(Point p1,Point p2)
11 {
12 return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
13 }
14
15 void Graham_scan(Point PointSet[],Point ch[],int n,int &len)
16 {
17 int i,j,k=0,top=2;
18 Point tmp;
19
20 for(i=1;i<n;i++)
21 if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))
22 k=i;
23 tmp=PointSet[0];
24 PointSet[0]=PointSet[k];
25 PointSet[k]=tmp;
26 for (i=1;i<n-1;i++)
27 {
28 k=i;
29 for (j=i+1;j<n;j++)
30 if ( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) ||
31 ((multiply(PointSet[j],PointSet[k],PointSet[0])==0)
32 &&(distance(PointSet[0],PointSet[j])<distance(PointSet[0],PointSet[k]))) )
33 k=j;
34 tmp=PointSet[i];
35 PointSet[i]=PointSet[k];
36 PointSet[k]=tmp;
37 }
38 ch[0]=PointSet[0];
39 ch[1]=PointSet[1];
40 ch[2]=PointSet[2];
41 for (i=3;i<n;i++)
42 {
43 while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
44 ch[++top]=PointSet[i];
45 }
46 len=top+1;
47 }
48