POJ 2932 Coneology（平面扫描/计算最外层圆个数）_综合

题目链接：
POJ 2932 Coneology
题意：
平面上有n个两两没有公共点的圆，i号圆的圆心在(xi,yi),半径为ri，编号从1开始。求所有最外层的，即不包含于其他圆内部的圆。输出符合要求的圆的个数和编号。n<=40000.
分析：

由于有任意两圆都没有公共点这一条件，要判断一个圆是否在其他圆内部，只要判断其圆心是否在其他圆内即可。这样判断每个圆是否是最外层的复杂度为 $O(N)$ ,因此很容易得到 $O(N^2)$ 复杂度的算法，但是这样显然会 $TLE$ 。
下面介绍平面扫描技术的 $O(NlogN)$ 复杂度算法。所谓平面扫描是指扫描线在平面上按给定轨迹移动的同时，不断根据扫描线扫过部分更新信息，从而得到整体所要求的结果的方法。扫描的方法，既可以从左向右与y轴平行的直线，也可以固定射线的端点逆时针转动。
对于这道题我们在从左向右平移与y轴平行的直线的同时，维护与扫描线相交的最外层的圆的集合。从左向右移动的过程中，只有扫描线移动到圆的左右两端时，圆与扫描线的相交关系才会发生变化。因此我们先将所有这样的x坐标枚举出来并排好序。(即 $ri-xi和ri+xi$ )
首先，我们来看一下扫描线移动到某个的左端时的情形。此时，我们需要判断该圆是否包含在其他圆中。为此，我们只需从当前与扫描线相交的外层圆中，找到上下两侧y坐标方向距离最近的两个圆，并检查它们就足够了。这是因为，假设该圆被包含与更远的圆中，却不被包含于最近的圆中，就会得到两圆相交的结论。这与题目所给的条件不符。于是，只要用二叉查找树来维护这些圆，就能够在 $O(logn)$ 的时间内取得待检查的圆了。
其次我们看一下扫描线移动到某个圆的右端时的情况。此时的处理很简单，如果该圆已经包含于其他圆中就什么也不做，如果是最外层的圆就将它从二叉树中删除。综上，总的复杂度为 $O(NlogN)$ 。

以上摘自《挑战程序设计竞赛》。

思考：
①：如果存在一排这样的圆，纵坐标和半径都一样只是横坐标不一样，那扫描线在扫描过程中，假设扫到了第i个圆
根据下面代码中的查找： $it=outers.lower_bound(make_pair(y[id],id));$ ，返回的it是什么呢？我们都知道 $lower_bound(k)$ 返回的是第一个>=k的迭代器，那么会返回代表i-1的迭代器吗？答案是不会的。因为在扫到第i个圆之前，就已经扫描到
第i-1个圆的右端了，所以集合中已经将第i-1圆“剔除”了，所以返回的应该是 $outers.begin()$ ,也就是第i圆也是合法圆。
②：假设一个集合s，s中并无元素y，删除y即 $s.erase(y)$ 对s并没有任何影响。

//5324K 1735MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
const int MAX_N=40010;int n;
double x[MAX_N],y[MAX_N],r[MAX_N];inline int inside(int i,int j) //判断圆i是否在圆j内
{double dx=x[i]-x[j],dy=y[i]-y[j];return dx*dx+dy*dy <= r[j]*r[j];
}int main()
{//freopen("2932in.txt","r",stdin);while(~scanf("%d",&n)){vector<pair<double,int> > events;for(int i=0;i<n;i++){scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);events.push_back(make_pair(x[i]-r[i],i)); //圆左端坐标events.push_back(make_pair(x[i]+r[i],i+n)); //圆右端坐标}sort(events.begin(),events.end()); //将所有圆左右端点排序//平面从左到右与y轴平行扫描set<pair<double,int> > outers; //与扫描线相交的最外层圆的集合，存储圆心纵坐标vector<int> res;for(int i=0;i<events.size();i++){int id=events[i].second % n;//printf("id=%d events[i].first=%.0lf\n",id,events[i].first);if(events[i].second<n){ //扫描到圆的左端set<pair<double,int> >::iterator it=outers.lower_bound(make_pair(y[id],id));//it是outers中在id圆上方的最接近id圆的迭代器if(it!=outers.end()&&inside(id,it->second)) continue;//it->second是上侧y坐标方向距离最近的圆编号if(it!=outers.begin()&&inside(id,(--it)->second)) continue;//(--it)->second是下侧y坐标方向距离最近的圆编号res.push_back(id);outers.insert(make_pair(y[id],id));} else { //扫描到圆的右端outers.erase(make_pair(y[id],id));}}sort(res.begin(),res.end());printf("%d\n",res.size());for(int i=0;i<res.size();i++){printf("%d%c",res[i]+1,i+1==res.size()?'\n':' ');}}return 0;
}