1328:Radar Installation

keyword

平面幾何　平面走査法　C++

概要

2次元平面上に点がN(<1000)個ある。x軸上に半径dの円を置いて全ての点をカバーしたい。最小でいくつ円を置く必要があるか求める問題。
例に漏れず平面走査法。イメージとしてはx軸上で円を左から右にずらしていく感じ。計算量O(N*log N)。

int xs[1009], ys[1009];
bool checked[1009];
int n, R;

int solve(){
    set< pair<double, int> > in, out;
    set<int> cur;
    for(int i=0; i<n; i++)
        checked[i] = false;
    for(int i=0; i<n; i++){
        if(abs((double)ys[i]) > R) return -1;
        in.insert(make_pair(xs[i]-sqrt(R*R-ys[i]*ys[i]), i));
        out.insert(make_pair(xs[i]+sqrt(R*R-ys[i]*ys[i]), i));
    }
    int ans = 0;
    while(!out.empty()){
        if(!in.empty() && in.begin()->first <= out.begin()->first){
            cur.insert(in.begin()->second);
            in.erase(in.begin());
        }
        else{
            int tar = out.begin()->second;
            if(!checked[tar]){
                ans++;
                for(set<int>::iterator it = cur.begin(); it != cur.end(); it++){
                    checked[*it] = true;
                }
            }
            cur.erase(tar);
            out.erase(out.begin());
        }
    }
    return ans;
}