凸包问题

#include #include 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>N; for(i=0;i>xy[i].x>>xy[i].y; if (xy[i].y<=xy[0].y&&xy[i].x=0) top--;//所有未向左传的点去掉 top++; stk[top]=i;//入栈 } for (i=1;i<=top;i++) fout< posted on 2007-06-30 11:02 姜雨生阅读(657) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

C++天空

凸包问题

导航

统计

常用链接

留言簿(1)

随笔档案

文章档案

搜索

最新评论