h_nosonの日記

競プロ、CTFなど

POJ 2932 Coneology

問題
2932 -- Coneology
平面上に円がN個あり,それらが交わることはない.
どの円にも囲まれていない円はいくつあるか.

解法
x座標の小さい方から走査していく.
走査する直線が円の左端にぶつかった時,その円が他の円に含まれているか調べる.
この時,調べる円はy座標で1つ上にある円と1つ下にある円だけで良い.
下の図が2つ上の円だけに囲まれた時のものになる.
この時1つ上の円はすでに囲まれているのでその円をカウントしなければよく,
結果1つ上と1つ下にある円だけで十分になる.
f:id:h_noson:20160427165041p:plain
ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,n,0)
#define REP(i,s,e) for (i = s; i < e; i++)
#define rep(i,n) REP(i,0,n)
#define INF 100000000

typedef long long ll;

double r[40000], x[40000], y[40000];

bool is_inside(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return r[i]*r[i] >= dx*dx + dy*dy;
}

int main() {
    int i, n;
    vector<pair<double,int>> cones;
    set<pair<double,int>> s;
    vector<int> ans;
    cin >> n;
    rep (i,n) {
        cin >> r[i] >> x[i] >> y[i];
        cones.push_back(make_pair(x[i]-r[i],i));
        cones.push_back(make_pair(x[i]+r[i],i+n));
    }
    sort(cones.begin(),cones.end());
    rep (i,2*n) {
        int id = cones[i].second;
        if (id < n) {
            set<pair<double,int>>::iterator it = s.lower_bound(make_pair(y[id],id));
            if (it != s.end() && is_inside(it->second,id)) continue;
            if (it != s.begin() && is_inside((--it)->second,id)) continue;
            ans.push_back(id+1);
            s.insert(make_pair(y[id],id));
        }
        else
            s.erase(make_pair(y[id-n],id-n));
    }
    sort(ans.begin(),ans.end());
    cout << ans.size() << endl;
    rep (i,ans.size())
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}