POJ 2932 Coneology - mayoko’s diary

蟻本の練習です。

問題

二次元平面上に N 個の円がある。これらの円は互いに交差しないことが保証されている。
「他の円の内部にない」という条件を満たす円を列挙せよ。

解法

蟻本 p231 の問題です。平面走査で解けます。

x 軸の小さい順に見ていきます。また, 「他の円の内部にない」という条件を満たす円の集合を S として持つことにします。

走査線が円 i の左端に来た時, その円を覆う可能性のある円は, 集合 S に入っている円のうち, y[i] に最も近い y 座標の円(上下 2 つ) しかありえません。
今 S に入っている円はその外部に円がないものなので, y[i] <= y[j] <= y[k] を満たす j, k について, i は j の内部にないけど k の内部にはあるとすると, j と k は交差することになり矛盾します。よって, y[i] の周辺上下 1 個ずつだけを調べれば良いので, 計算量は O(N log N) で実現できます。

const int MAXN = 40040;
double X[MAXN], Y[MAXN], R[MAXN];

// i が j の中にあるか
bool isIn(int i, int j) {
    double dx = X[i]-X[j], dy = Y[i]-Y[j];
    return dx*dx+dy*dy <= R[j]*R[j];
}

int main() {
    int N;
    scanf("%d", &N);
    vector<pii> ps;
    for (int i = 0; i < N; i++) {
        scanf("%lf %lf %lf", R+i, X+i, Y+i);
        ps.push_back(make_pair(X[i]-R[i], i));
        ps.push_back(make_pair(X[i]+R[i], N+i));
    }
    sort(ps.begin(), ps.end());
    set<pair<double, int> > S;
    vector<int> ans;
    for (int i = 0; i < 2*N; i++) {
        pii p = ps[i];
        if (p.second < N) {
            set<pair<double, int> >::iterator it = S.lower_bound(pii(Y[p.second], 0));
            bool ng = false;
            if (it != S.end()) {
                ng |= isIn(p.second, it->second);
            }
            if (it != S.begin()) {
                it--;
                ng |= isIn(p.second, it->second);
            }
            if (!ng) {
                ans.push_back(p.second);
                S.insert(pii(Y[p.second], p.second));
            }
        } else {
            p.second -= N;
            S.erase(pii(Y[p.second], p.second));
        }
    }
    sort(ans.begin(), ans.end());
    int sz = ans.size();
    printf("%d\n", sz);
    for (int i = 0; i < sz; i++) {
        printf("%d%c", ans[i]+1, (i<sz-1 ? ' ' : '\n'));
    }
    return 0;
}