poj 2932 Coneology （扫描线）

题意

平面上有N个两两不相交的圆，求全部最外层的，即不被其它圆包括的圆的个数并输出

思路

挑战程序竞赛P259页

代码

/* **********************************************

Auther: xueaohui

Created Time: 2015-7-25 16:56:13

File Name   : poj2932.cpp

*********************************************** */

#include <iostream>

#include <fstream>

#include <cstring>

#include <climits>

#include <deque>

#include <cmath>

#include <queue>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <utility>

#include <sstream>

#include <complex>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <ctime>

#include <bitset>

#include <functional>

#include <algorithm>

using namespace std;

#define ll long long

#define N 111111

int n;

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

bool inside(int i,int j){

    double px = x[i]-x[j];

    double py = y[i]-y[j];

    return px*px+py*py<=r[j]*r[j];

}

void slove(){

    vector<pair<double,int>>e;

    e.clear();

    for(int i=0;i<n;i++){

        e.push_back(make_pair(x[i]-r[i],i));

        e.push_back(make_pair(x[i]+r[i],i+n));

    }

    sort(e.begin(),e.end());

    set<pair<double,int>>out;

    vector<int>res;

    res.clear();

    out.clear();

    for(int i=0;i<e.size();i++){

        int id = e[i].second %n;

        if(e[i].second<n){

            set<pair<double,int>>::iterator it = out.lower_bound(make_pair(y[id],id));

            if(it != out.end() && inside (id,it->second)) continue;

            if(it != out.begin() && inside (id ,(--it)->second)) continue;

            res.push_back(id);

            out.insert(make_pair(y[id],id));

        }

        else{

            out.erase(make_pair(y[id],id));

        }

    }

    sort(res.begin(),res.end());

    printf("%d\n",res.size());

    for(int i=0;i<res.size();i++){

       if(i!=0) printf(" ");

       printf("%d",res[i]+1);

    }

    printf("\n");

}

int main(){

    while(scanf("%d",&n)==1){

    for(int i=0;i<n;i++){

        scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);

    }

    slove();

    }

}