关于凸包的算法 帮忙查看一下原因啊 麻烦啦
输入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);
}