依然是圆有关的扫描线.感觉额.上一篇说得自己都看不太懂的样子.
这个题目吧。是要问你有哪个圆没有被其他的圆覆盖住.说白了就是他的被覆盖层数为0.和上一篇的题相比.简单了点。
同样的.没有相交的圆..
啊.直接说做法.加入set的集合的元素是.额.是不相互包含的圆.也就是说两两关系是相离.那么一个圆只要和它上下两圆无关系，自然也不会和这之外的圆有关系了.
然后这里判断一个圆的上下，就没有那么麻烦了.按圆心位置高下来就行.即能和当前圆发生关系的就只有它上下的圆。毕竟加入set的集合的圆都是没有关系的.
额......老是感觉没说清的感觉......
好吧.硬着头皮上我的cuo代码.....set的操作害我RE了好几次...
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include <cmath>
#include<algorithm>
using namespace std;
const int L=50001;
const double eps=0.0;
struct point
{
double x,y,r;
int va,id;
}cir[L];
struct node
{
double x;
int id,flag;
}lr[L*2];
set<int> seg;
typedef set<int>::iterator it;
bool cmp(point a,point b)
{
return a.y<b.y || a.y==b.y && a.x<b.x;
}
bool cmp1(node a,node b)
{
return a.x<b.x;
}
bool pr(point a,point b)
{
return a.x==b.x && a.y==b.y;
}
double dis(point a,point b)
{
a.x-=b.x;a.y-=b.y;
return sqrt(a.x*a.x+a.y*a.y);
}
int check(point a,point b)
{
if(pr(a,b))
if(a.r>b.r-eps) return 1;
if(a.r<b.r) return 0;
double d=dis(a,b);
if(d<a.r-b.r-eps) return 1;
return 0;
}
void slove(int n)
{
int i,j;
for(i=0;i<n;i++)
{
if(lr[i].flag==0)
{
it idx=seg.insert(lr[i].id).first;
it be=idx,ed=idx;
if(seg.size()>=2)
{
if(be==seg.begin())
{
j=*++be;
if(check(cir[j],cir[lr[i].id]))
{
cir[lr[i].id].va=1;
seg.erase(lr[i].id);
}
}
else if(++ed==seg.end())
{
j=*--be;
if(check(cir[j],cir[lr[i].id]))
{
cir[lr[i].id].va=1;
seg.erase(lr[i].id);
}
}
else
{
ed--;
if((check(cir[*--be],cir[lr[i].id])) || (check(cir[*++ed],cir[lr[i].id])))
{
cir[lr[i].id].va=1;
seg.erase(lr[i].id);
}
}
}
}
else
seg.erase(lr[i].id);
}
}
int ans[L];
int main()
{
int i,j,n,m;
while(~scanf("%d",&n))
{
j=0;
for(i=0;i<n;i++)
{
scanf("%lf %lf %lf",&cir[i].r,&cir[i].x,&cir[i].y);
cir[i].id=i;
cir[i].va=0;
}
sort(cir,cir+n,cmp);
for(i=0;i<n;i++)
{
lr[j].id=i;lr[j].x=cir[i].x-cir[i].r;lr[j++].flag=0;
lr[j].id=i;lr[j].x=cir[i].x+cir[i].r;lr[j++].flag=1;
}
sort(lr,lr+j,cmp1);
slove(j);
j=0;
for(i=0;i<n;i++)
if(cir[i].va==0) ans[j++]=cir[i].id+1;
printf("%d\n",j);
sort(ans,ans+j);
for(i=0;i<j;i++)
printf("%d%c",ans[i],i==j-1?'\n':' ');
}
return 0;
}