题意:
给出一些不相交的圆,问有多少个圆不被其他圆包围
题解:
扫描线,把所有圆的左边界和右边界放到\(vector\)里排序,遍历到圆左边界的时候判断是否满足条件,到右边界的时候把这个圆从\(set\)中删掉,对于一个选到当前左边界的圆,因为不存在相交,所以只需要判断与他\(y\)坐标最近的两个在\(set\)中的圆是否包含他即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
void ____(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int MAXN = 4e4+7;
int n;
double x[MAXN],y[MAXN],r[MAXN];
bool check(int ida, int idb){
/* check if circle[ida] include in circle[idb] */
double dx = x[ida] - x[idb], dy = y[ida] - y[idb];
return r[idb] * r[idb] > dx * dx + dy * dy;
}
void solve(){
for(int i = 1; i <= n; i++) scanf("%lf %lf %lf",&r[i],&x[i],&y[i]);
vector<pair<double,int> > vec;
for(int i = 1; i <= n; i++){
vec.push_back(make_pair(x[i]-r[i],i));
vec.push_back(make_pair(x[i]+r[i],-i));
}
set<pair<double,int> > S;
vector<int> V;
sort(vec.begin(),vec.end());
for(int i = 0; i < (int)vec.size(); i++){
int id = abs(vec[i].second);
if(vec[i].second<0) S.erase(make_pair(y[id],id));
else{
set<pair<double,int> >::iterator it = S.lower_bound(make_pair(y[id],-1));
bool inc = false;
if((it!=S.end() and check(id,it->second)) or (it!=S.begin() and check(id,(--it)->second))) inc = true;
if(!inc) S.insert(make_pair(y[id],id)), V.push_back(id);
}
}
printf("%d\n",V.size());
sort(V.begin(),V.end());
for(int i = 0; i < (int)V.size(); i++) printf("%d ",V[i]);
puts("");
}
int main(){
while(scanf("%d",&n)!=EOF) solve();
return 0;
}