求证做法 / 求hack
查看原帖
求证做法 / 求hack
1013955
1234567890sjx楼主2024/10/9 22:16
const int N=1000010,mod=1e9+7;
#define x first
#define y second
PII z[N],zz[N];int p[N];
PII operator-(const PII &a,const PII &b){
    return {a.x-b.x,a.y-b.y};
}
int cross(PII a,PII b){
    return a.x*b.y-a.y*b.x;
}
int sgn(int x){
    if(x>0)return 1;
    if(x<0)return -1;
    return 0;
}
int chk(PII a,PII b,PII c,PII d){
    int v1=cross(b-a,c-a),v2=cross(b-a,d-a),v3=cross(d-c,b-c),v4=cross(d-c,a-c);
    return sgn(v1)*sgn(v2)<=0&&sgn(v3)*sgn(v4)<=0;
}
void solve(unsigned __testid=1){
    int n;cin>>n;
    F(i,1,n)cin>>z[i].x>>z[i].y;
    F(i,1,n)cin>>zz[i].x>>zz[i].y;
    F(i,1,n)p[i]=i;
    while(1){
        int ok=0;
        F(i,1,n)F(j,i+1,n)if(chk(z[i],zz[p[i]],z[j],zz[p[j]]))ok=1,swap(p[i],p[j]);
        if(!ok)break;
    }
    F(i,1,n)cout<<p[i]<<' ';cout<<'\n';
}
2024/10/9 22:16
加载中...