发布时间：2024-07-31

极角排序

atan2法(double时使用)

象限顺序3 4 1 2

double theta(auto p){
    return atan2(p.y,p.x);
}
void psort(vector<Point> &p,Point c=Point(0,0)){
    sort(p.begin(),p.end(),[&](auto a,auto b){
        return cmp(theta(a-c),theta(b-c))<0;
    });
}

叉乘法1(整数时使用)

象限顺序1 2 3 4

int quadrand(Point p){
    return (p.y<0)<<1|(p.x<0)^(p.y<0);
}
void psort(vector<Point> &p,Point c=Point(0,0)){
    sort(p.begin(),p.end(),[&](auto a,auto b){
        return quadrand(a-c)<quadrand(b-c)||quadrand(a-c)==quadrand(b-c)&&cross(a-c,b-c)>0;
    });
}

叉乘法2

象限顺序2 3 4 1,如果两个点共线，那么较近的点更小

sort(tmp.begin(),tmp.end(),[&](auto x,auto y){
    int c=cross(x-p[t],y-p[t]);
    if(c==0)return dot(x-p[t],x-p[t])<dot(y-p[t],y-p[t]);
    if(((x-p[t]).x<0)!=((y-p[t]).x<0))return (x-p[t]).x<(y-p[t]).x;
    return c>0;
});