2017-team2/geometry

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

struct point{
    int x,y;
};

long long cross(point a,point b){
    return 1LL*a.x*b.y-1LL*a.y*b.x;
}
point operator -(const point a,const point b){
    return (point){a.x-b.x,a.y-b.y};
}
int judge(point t,point st[],int top){  //judge whether the point is inside the ConvexHull(Unclockwise)
    int l=2,r=top-1;
    while(l<=r){
        int mid=(l+r)>>1;
        point a=st[1],b=st[mid],c=st[mid+1];
        long long c1=cross(b-a,t-a),c2=cross(c-a,t-a); 
        if (c1>=0&&c2<=0) return cross(c-b,t-b)>=0;
        if (c1<0) r=mid-1; else l=mid+1;
    }
    return 0;
}

by Team4 JYW

struct point{

int x,y;

};

long long cross(point a,point b){

return 1LL*a.x*b.y-1LL*a.y*b.x;

}

point operator -(const point a,const point b){

return (point){a.x-b.x,a.y-b.y};

}

int judge(point t,point st[],int top){ //judge whether the point is inside the ConvexHull(Unclockwise)

int l=2,r=top-1;

while(l<=r){

int mid=(l+r)>>1;

point a=st[1],b=st[mid],c=st[mid+1];

long long c1=cross(b-a,t-a),c2=cross(c-a,t-a);

if (c1>=0&&c2<=0) return cross(c-b,t-b)>=0;

if (c1<0) r=mid-1; else l=mid+1;

}

return 0;

}

by Team4 JYW