AOJ 0552 Exposition - NOSSの雑記

問題

JOI 2010 本戦の問題

問題リンク：AOJ 0552

解法

かなり難しかった。

そのままの座標だとマンハッタン距離が扱いずらいので45度回転をする。すると、例えば $s=x+y,t=x-y$ と変換すれば距離は $\max(|s_i-s_j|, |t_i-t_j|)$ で求められるようになる。点群の最遠点対の距離は $\max(s_{\rm max}-s_{\rm min}, t_{\rm max}-t_{\rm min})$ で求まり、s,tで分離して考えられるので扱いやすくなる。

最大値の最小化なので二分探索が適用できないか考える。距離x以下で2つのグループに分けられるかを判定できればよい。このときボトルネックとなるのは全体の $s_{\rm max},s_{\rm min}, t_{\rm max},t_{\rm min}$ なのでこれらを基準にすると、例えば $s_i-s_{\rm min} > x$ となる点iは絶対に $s_{\rm min}$ の点と同じグループにできないことがわかる。これをそれぞれについて判定すると点を9つの領域に分類できる。

真ん中の列、行にある点は後で都合がいいように割り振れるので無視する。問題になるのは四隅の領域で、いずれかの対角の領域(図の0,3のペアと1,2のペア)にある点の個数が0でないと2つのグループに分けられない。

f:id:NOSS:20200215104917p:plain — 右下の黒い点は赤青どちらにも属せない

逆にある対角の点の個数が0ならば分けられるのでこれで判定を行える。

一回の判定にかかる計算量は $O(N)$ なので全体の計算量は $O(N \log (|X|+|Y|))$ となる。

Code

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1<<30;

void chmin(int &a, int b){a=min(a,b);}
void chmax(int &a, int b){a=max(a,b);}

int n, smax = -INF, smin = INF, tmax = -INF, tmin = INF;
vector<int> s, t;

// 距離x以下で分割できるか
bool check(int x){
    vector<int> gs(n,2), gt(n,2);
    // 45度回転した平面で9つの領域に分類
    for(int i=0;i<n;i++){
        if(min(abs(s[i]-smin),abs(s[i]-smax)) > x) return false;
        else if(abs(s[i]-smax) > x) gs[i] = 0;
        else if(abs(s[i]-smin) > x) gs[i] = 1;
    }
    for(int i=0;i<n;i++){
        if(min(abs(t[i]-tmin),abs(t[i]-tmax)) > x) return false;
        else if(abs(t[i]-tmax) > x) gt[i] = 0;
        else if(abs(t[i]-tmin) > x) gt[i] = 1;
    }
    int cnt[4]{};
    for(int i=0;i<n;i++){
        if(gs[i]==0 && gt[i]==0) cnt[0]++;
        if(gs[i]==0 && gt[i]==1) cnt[1]++;
        if(gs[i]==1 && gt[i]==0) cnt[2]++;
        if(gs[i]==1 && gt[i]==1) cnt[3]++;
    }
    return (cnt[0]+cnt[3]==0 || cnt[1]+cnt[2]==0);
}

int main(){
    cin >> n;
    s.resize(n);
    t.resize(n);
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        s[i] = x+y;
        t[i] = x-y;
        chmax(smax, s[i]); chmin(smin, s[i]);
        chmax(tmax, t[i]); chmin(tmin, t[i]);
    }
    int ok = 1e6, ng = 0;
    while(abs(ok-ng)>1){
        int mid = (ok+ng)/2;
        if(check(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok << endl;
    return 0;
}