随笔 - 87  文章 - 279  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214330
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

用差积做极角排序,减少浮点误差

#include  < iostream >
#include 
< algorithm >
using   namespace  std;

typedef 
int  XYType;

struct  POINT  {
    XYType x, y;
}
 ps;

XYType cross(POINT p1, POINT p2, POINT p0) 
{
    
// 求矢量[p0,p1],[p0,p2]的差积;
     return  (p1.x  -  p0.x)  *  (p2.y  -  p0.y)  -  (p2.x  -  p0.x)  *  (p1.y  -  p0.y);
}


int  cmp(POINT p1, POINT p2)  {
    
// 以ps为中心的极角排序
    XYType ax, ay, bx, by;
    ax 
=  p1.x  -  ps.x; ay  =  p1.y  -  ps.y;
    bx 
=  p2.x  -  ps.x; by  =  p2.y  -  ps.y;
    
if  (ay  *  by  <=   0 return  by  >  ay  ||  (by  ==  ay  &&  bx  >  ax);
    XYType ret 
=  cross(p1, p2, ps);
    
if  (ret  >   0 return   1 ;
    
if  (ret  ==   0 return  bx  >  ax;
    
if  (ret  <   0 return   0 ;
    
return   1 ;
}
;

int  main()  {
    freopen(
" test.txt " " r " , stdin);
    POINT arrP[
100 ];
    
int  n  =   0 , i, beg;
    
int  stack[ 100 ], top;    
    
while  (scanf( " %d%d " & arrP[n].x,  & arrP[n].y)  !=  EOF) n ++ ;
    
for  (i = 1 ; i < n; i ++ {
        
if  (arrP[i].y  <  arrP[ 0 ].y  ||  (arrP[i].y  ==  arrP[ 0 ].y  &&  arrP[i].x  <  arrP[ 0 ].x)) 
            swap(arrP[
0 ], arrP[i]);
    }

    ps.x 
=  arrP[ 0 ].x; ps.y  =  arrP[ 0 ].y;
    sort(arrP
+ 1 , arrP + n, cmp);
    
for  (i = 0 ; i <= 2 ; i ++ ) stack[i]  =  i;
    top 
=   2 ;
    
for  (i = 3 ; i < n; i ++ {
        
while  (cross(arrP[stack[top]], arrP[i], arrP[stack[top - 1 ]])  <   0 {
            top
-- ;
        }

        stack[
++ top]  =  i;
    }

    
for  (i = 0 ; i <= top; i ++ {
        
if  (arrP[stack[i]].x  ==   0   &&  arrP[stack[i]].y  ==   0 {
            beg 
=  i;
            
break ;
        }

        
// printf("(%d,%d)\n", arrP[stack[i]].x, arrP[stack[i]].y);
    }

    
for  (i = beg; i <= top + beg; i ++ {
        
int  k  =  i  >  top  ?  i  -  top  -   1  : i;
        printf(
" (%d,%d)\n " , arrP[stack[k]].x, arrP[stack[k]].y);
    }

    
return   0 ;
}
posted on 2007-03-25 02:43 阅读(1155) 评论(1)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 凸包... 2007-06-30 10:26 姜雨生
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream fin ("bag.in");
ofstream fout ("bag.out");
struct xys
{
int x;
int y;
};
int N;//数目
xys xy[101];//坐标系
int top;//堆栈顶
int stk[101];//堆栈
void swap(xys *a,xys *b)
{
xys tmp = *a;
*a = *b;
*b =tmp;
}
int multi(xys a,xys b,xys c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);//求叉积
}
bool comp(xys p1,xys p2)
{
int t;
t=multi(p1,p2,xy[0]);
if ((t>=0)&&((p1.x-xy[0].x)+(p1.y-xy[0].y)<(p2.x-xy[0].x)+(p2.y-xy[0].y)))
return true;//叉积正确
return false;
}
void sort(int p,int r)
{
int i,j;
xys x;
if (r-p+1<=5)
{
for (j=p+1;j<=r;j++)
{
i=j;
while(i>1&&comp(xy[i],xy[i-1]))
{
swap(&xy[i],&xy[i-1]);//交换元素
i--;
}
}
}
else
{
x=xy[p+rand()%(r-p+1)];//随即选区一个支点
i=p,j=r;
do
{
while (comp(xy[i],x))i++;
while (comp(x,xy[j]))j--;
if (i<j)swap(&xy[i],&xy[j]);
}//一次规划
while (i<j);
sort(p,j);//前半部
sort(p+1,r);//后半部
}
}
void init()
{
int i;
fin>>N;
for(i=0;i<N;i++){
fin>>xy[i].x>>xy[i].y;
if (xy[i].y<=xy[0].y&&xy[i].x<xy[0].y) swap(xy[0],xy[i]);//交换
}
sort(1,N-1);
}
void graham()
{
int i;
for(i=1;i<=3;i++) stk[i]=i-1;
top=3;
for(i=3;i<N;i++)
{
while(multi(xy[i],xy[stk[top]],xy[stk[top-1]])>=0) top--;//所有未向左传的点去掉
top++;
stk[top]=i;//入栈
}
for (i=1;i<=top;i++)
fout<<xy[stk[i]].x<<" "<<xy[stk[i]].y<<endl;
}
int main (void)
{
init();
graham();//扫描出凸包,打印
return 0;
}  回复  更多评论
  

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