POJ 2932 Coneology
蟻本の練習です。
解法
蟻本 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; }