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\n",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;

}

巴特西

POJ2932 Coneology【圆扫描线】

题意：

题解：

最新文章

热门文章