POJ 2932 平面扫描 /// 判断圆的包含关系

题目大意：

平面上有n个两两不相交的圆，给定圆的圆心（x，y）和半径 r

求所有最外层的 即 不包含于其他圆内部的圆

挑战258页 平面扫描

记录所有圆的左端和右端 排序后 逐一扫描

将到当前圆为止的最外层的圆存入数组

当遇到一个圆的左端

判断 这个圆 是否被 离它最近的上下的两个已存入的最外层的圆 包含

若被包含 则跳过该圆

若未被包含 说明其是一个最外层的圆 存入数组

这里不会有 它包含上下其中某个圆 的情况出现

因为包含某个圆 那么 该圆的左端 必定位于 被包含圆的左端的左边

但是平面扫描限制了 该圆的左端必定位于 已知的最外层的圆的左端的右边

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <set>

#include <vector>

#define F first

#define S second

#define P pair<double,int>

using namespace std;

const int N=+;

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

/*圆i是否包含在圆j内

    dx*dx+dy*dy 两圆圆心距 的平方

    若小于圆j的半径的平方

    则i包含于j内

这里的前提是所有圆两两不相交

*/

bool inside(int i,int j)

{

    double dx=x[j]-x[i], dy=y[j]-y[i];

    return dx*dx+dy*dy<=r[j]*r[j];

}

int main()

{

    vector <P> vec;

    int n; scanf("%d",&n);

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

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

        vec.push_back(P(x[i]-r[i],i)); // 左端

        vec.push_back(P(x[i]+r[i],i+n)); // 右端 i+n便于和左端点区别开

    }

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

    set <P> s;

    vector <int> ans;

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

        int id=vec[i].S;

        if(id<n) { // 左端点

            set <P> ::iterator it=s.lower_bound(P(y[id],id));

            // 找到id上面的圆

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

            // 判断上面的圆有没有包含id

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

            // 判断下面的圆有没有包含id

            ans.push_back(id);

            s.insert(P(y[id],id));

        }

        else s.erase(P(y[id%n],id%n)); // 右端点

        // 之后出现的圆不可能于该圆有任何包含关系 将该圆去掉

    }

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

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

    for(int i=;i<ans.size();i++)

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

    printf("\n");

    return ;

}