hurrican6

C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 1 Stories :: 0 Comments :: 0 Trackbacks
 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 
posted on 2010-06-25 22:03 comix 阅读(112) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理