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
          
           
?