| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 518 人关注过本帖
标题:关于凸包的算法 帮忙查看一下原因啊 麻烦啦
取消只看楼主 加入收藏
lei274002948
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2010-12-9
收藏
 问题点数:0 回复次数:0 
关于凸包的算法 帮忙查看一下原因啊 麻烦啦
输入n值 再输入n个坐标  输出 凸包 顶点个数k
以下是代码  编译连接能通过 但输入数据 后 发现有错误
是指针的问题   问题就是 qsort那个  把 Vertex+1 改成Vertex就能输出结果
当然 结果不正确  但是为什么 Vertex+1 就不能运行呢   还是那个cmp 写错了?
很闹心   谢谢各位了


#include <iostream>
using namespace std;

#define N 10000
struct Point {
 int x;
 int y;
};
 

Point Vertex[N];
Point Stack[N];
int n  ;                  // 节点数目
int mul(Point a,Point b,Point z);           //叉积
int dist(Point a,Point z);             //距离
int cmp(const void *p,const void *q);         
int Graham();

int main()
{
    int num;
 cin>>num;
   for(int i=0;i<num;i++)
    cin>>Vertex[i].x>>Vertex[i].y;
   int res=Graham();
   cout<<res<<endl;
}

int  Graham(){

 int i=0;
 int k=0;
 Point tmp;
 for(i=1;i<n;i++)
  if(Vertex[i].y<Vertex[k].y||(Vertex[i].y==Vertex[k].y&&Vertex[i].x<Vertex[k].x))
   k=i;
 if(k!=0){
 tmp=Vertex[0];
 Vertex[0]=Vertex[k];
 Vertex[k]=tmp;}
 Stack[0]=Vertex[0];
 qsort( Vertex+1,n-1,sizeof(Point),cmp);      
 Stack[1]=Vertex[1];
 Stack[2]=Vertex[2];
 k=2;
    for(i=3;i<n;i++)
 {
  while(mul(Stack[k],Vertex[i],Stack[k-1])<0)
   k--;
  Stack[++k]=Vertex[i];
 }
 if(mul(Stack[k],Vertex[0],Stack[k-1])<0)
  k--;
 return k;

}



int cmp(const void *p,const void *q)
{
    Point   a;
  Point   b;
 a= *(Point*)(p) ;
 b=*(Point*)(q);
 int k=mul( a, b,Vertex[0]);
    if(k>0)
  return -1;
 if(k==0)
  return dist( a,Vertex[0])-dist( b,Vertex[0]);
 return 1;
}

int dist(Point a,Point z)
{
 return (a.x-z.x)*(a.x-z.x)+(a.y-z.y)*(a.y-z.y);
}

int mul(Point p1,Point p2,Point p0)//判断向量夹角cos的正负
{
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
搜索更多相关主题的帖子: 算法 凸包 麻烦 
2010-12-09 22:41
快速回复:关于凸包的算法 帮忙查看一下原因啊 麻烦啦
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024945 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved