求助二维凸包
  • 板块学术版
  • 楼主TerryGong
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/28 21:14
  • 上次更新2023/11/4 08:41:34
查看原帖
求助二维凸包
167689
TerryGong楼主2021/8/28 21:14

各位大佬们,请问此代码问题在哪?

inline double sqr(double x){return x*x;}
inline double sqrdist(node A,node B){return sqr(A.x-B.x)+sqr(A.y-B.y);}
inline double angle(node O,node A,node B){double o=sqrdist(A,B),a=sqrdist(B,O),b=sqrdist(A,O);return (a+b-o)/(2*sqrt(a*b));}
inline int isLeft(node p0,node p1,node p2){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
inline int getint(double x){return int(x+0.5);}
int n,bot=0,top=-1;
double m;
void chainhull(){
    int minmin=0,minmax,i;double xmin=p[0].x;
    for(i=1;i<n;i++)
        if(p[i].x!=xmin)
            break;
    minmax=i-1;
    if(minmax==n-1){
        st[++top]=p[minmin];
        if(p[minmax].y!=p[minmin].y)
            st[++top]=p[minmax];
        st[++top]=p[minmin];
        return;
    }
    int maxmin,maxmax=n-1;double xmax=p[n-1].x;
    for(i=n-2;i>=0;i--)
        if(p[i].x!=xmax)
            break;
    maxmin=i+1;
    st[++top]=p[minmin];
    i=minmax;
    while(++i<=maxmin){
        if(isLeft(p[minmin],p[maxmin],p[i])>=0&&i<maxmin)
            continue;
        while(top>0){
            if(isLeft(st[top-1],st[top],p[i])>0)break;
            else top--;
        }
        st[++top]=p[i];
    }
    if(maxmax!=maxmin)
        st[++top]=p[maxmax];
    i=maxmin;bot=top;
    while(--i>=minmax){
        if(isLeft(p[maxmax],p[minmax],p[i])>=0&&i>minmax)continue;
        while(top>bot){
            if(isLeft(st[top-1],st[top],p[i])>0)break;
            else top--;
        }
        st[++top]=p[i];
    }
    if(minmax!=minmin)
        st[++top]=p[minmin];
    return;
}

代码中:

  • stack[]为栈,p[]为点
  • p[]已经按照bool operator< (const node &q)const{return x==q.x?y<q.y:x<q.x;}排序完毕

问题:

  • 此代码为什么结果是 231-2^{31}
  • 此代码中 stack[] 数组存储的是凸包的点吗?

蒟蒻求助

2021/8/28 21:14
加载中...