裏紙

ほぼ競プロ、たまに日記

CF 958 E3 - Guard Duty (hard)

問題

Problem - E3 - Codeforces

問題概要

N個の白い点とN個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。

  •  1 \le N \le 10000
  •  |x|,|y| \le 10000
  • 2点が同じ位置にある・3点が同じ直線上にのることはない

イデア

(いきなり)余談だが、このように交差しないマッチングを作ることは必ず出来る。そのようなマッチングとは、線分の長さの合計が最小になるような割り当て方である。仮に、このマッチングに対して交差があるような線分があると仮定する。線分B_0 W_1B_1 W_0が交差するとき、これらはB_0 W_0B_1 W_1の組に繋ぎ替えれば交差はなくなる。そして、この線分の長さの合計は、三角不等式から前者よりも短くなっていることが分かる。

さて、このようなマッチングをどのように構築するかを考える。上で述べたように、白の点と黒の点が同じ個数なら、必ず題意を満たすマッチングを作ることが可能である。よって、1つのマッチングを構成して、それによって出来る線分に対して、領域が2つに分割される時に両方の領域でまた白の点と黒の点が同じ個数になるような線分を常に選び続ける事ができれば、このマッチングは完成する。

今回は、その領域内で、x座標が最小の位置にある点bとどれをマッチングさせるかを考える。この時に、点bを基準にして偏角ソートしておき、その順番で点bを同じなら+1、違うなら-1という風にカウントしていくと、初めはカウンターが0からスタートし、最終的には(領域内には白と黒は同じ個数あり、基準にする点として1つ使っているので)-1でカウンターが止まる。このカウンターが-1になる瞬間に、その点とbを結ぶことにすれば、それより上と下の領域が両方ともまた白の点と黒の点が同じ個数になる。

これを繰り返して、全てのマッチングが終了するまで試せば良い。これは全部でN回行い、1回の動作の中ではソートをするので、全体としてO(N^2 log N)で解くことが出来る。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;

// (x,y), (spaceship/base, ID)
using Point = pair<pi,pi>;

int main(){
    int N;
    scanf(" %d", &N);

    vector<Point> pts;
    rep(i,2){
        rep(j,N){
            int x,y;
            scanf(" %d %d", &x, &y);
            pts.pb({{x,y},{i,j}});
        }
    }
    sort(all(pts));

    vector<int> ans(N);

    queue<vector<Point>> que;
    que.push(pts);
    while(!que.empty()){
        vector<Point> p = que.front();
        que.pop();
        int n = p.size();

        // 基準点としてx座標最小の点を選ぶ
        Point b = p[0];
        rep(i,n){
            p[i].fi.fi -= b.fi.fi;
            p[i].fi.se -= b.fi.se;
        }
        b = p[0];

        // 基準点からの偏角でソート
        vector<pair<double,int>> args;
        for(int i=1; i<n; ++i){
            double rad = atan2(p[i].fi.se, p[i].fi.fi);
            args.pb({rad,i});
        }
        sort(all(args));

        // bと線を引く相手wを探す
        Point w;
        int ct = 0;
        rep(i,n-1){
            int idx = args[i].se;

            if(b.se.fi == p[idx].se.fi) ++ct;
            else --ct;

            if(ct == -1){
                // このタイミングで分割することで、この線分より上も下もbalancedが保たれる
                w = p[idx];
                break;
            }
        }

        // bのマッチング相手が決定
        if(b.se.fi == 0) ans[b.se.se] = w.se.se;
        else ans[w.se.se] = b.se.se;

        // 直線 b-w で2つの領域に分割して部分問題を解く
        // Ax+By+C=0
        int A = w.fi.se - b.fi.se;
        int B = b.fi.fi - w.fi.fi;
        int C = b.fi.se*w.fi.fi - b.fi.fi*w.fi.se;

        vector<Point> l,r;
        rep(i,n){
            int x = p[i].fi.fi, y = p[i].fi.se;
            int val = A*x + B*y + C;

            if(val>0) l.pb(p[i]);
            else if(val<0) r.pb(p[i]);
        }
        if(!l.empty()) que.push(l);
        if(!r.empty()) que.push(r);
    }

    rep(i,N) printf("%d\n", ans[i]+1);
    return 0;
}