POJ2932 Coneology【圆扫描线】

POJ2932 Coneology

题意：

给出一些不相交的圆，问有多少个圆不被其他圆包围

题解：

扫描线，把所有圆的左边界和右边界放到(vector)里排序，遍历到圆左边界的时候判断是否满足条件，到右边界的时候把这个圆从(set)中删掉，对于一个选到当前左边界的圆，因为不存在相交，所以只需要判断与他(y)坐标最近的两个在(set)中的圆是否包含他即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
void ____(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int MAXN = 4e4+7;
int n;
double x[MAXN],y[MAXN],r[MAXN];
bool check(int ida, int idb){
    /* check if circle[ida] include in circle[idb] */
    double dx = x[ida] - x[idb], dy = y[ida] - y[idb];
    return r[idb] * r[idb] > dx * dx + dy * dy;
}
void solve(){
    for(int i = 1; i <= n; i++) scanf("%lf %lf %lf",&r[i],&x[i],&y[i]);
    vector<pair<double,int> > vec;
    for(int i = 1; i <= n; i++){
        vec.push_back(make_pair(x[i]-r[i],i));
        vec.push_back(make_pair(x[i]+r[i],-i));
    }
    set<pair<double,int> > S;
    vector<int> V;
    sort(vec.begin(),vec.end());
    for(int i = 0; i < (int)vec.size(); i++){
        int id = abs(vec[i].second);
        if(vec[i].second<0) S.erase(make_pair(y[id],id));
        else{
            set<pair<double,int> >::iterator it = S.lower_bound(make_pair(y[id],-1));
            bool inc = false;
            if((it!=S.end() and check(id,it->second)) or (it!=S.begin() and check(id,(--it)->second))) inc = true;
            if(!inc) S.insert(make_pair(y[id],id)), V.push_back(id);
        }
    }
    printf("%d
",V.size());
    sort(V.begin(),V.end());
    for(int i = 0; i < (int)V.size(); i++) printf("%d ",V[i]);
    puts("");
}
int main(){
    while(scanf("%d",&n)!=EOF) solve();
    return 0;
}