poj 2932 Coneology 掃面線法
題意：
給n個無交點的圓，求這n個圓中不被其它圓包含的圓。
分析：
掃面線法，用二叉樹（set+lowerbound方法）維護最外圓的集合。
代碼：
#include
#include
#include
#include
using namespace std;
const int maxN=40012;
double r[maxN],x[maxN],y[maxN];
int n;
vector > events;
set > outers;
vector res;
bool inside(int i,int j)
{
double dx=x[i]-x[j],dy=y[i]-y[j],dr=r[i]-r[j];
return r[i]<=r[j]&&dx*dx+dy*dy<=dr*dr;
}
int main()
{
scanf("%d",&n);
for(int i=0;i >::iterator it=outers.lower_bound(make_pair(y[ids],ids));
if(it!=outers.end()&&inside(ids,it->second)) continue;
if(it!=outers.begin()&&inside(ids,(--it)->second)) continue;
res.push_back(ids);
outers.insert(make_pair(y[ids],ids));
}else
outers.erase(make_pair(y[ids],ids));
}
sort(res.begin(),res.end());
printf("%d\n",res.size());
for(int i=0;i
