提交记录

//省略计算几何板子
const int N=5e5+10,inf=1e8+10;
struct circle{
   Point o;
   LD r;
   void in(){o.in();scanf("%lf",&r);}
   void in1(){o.in();r=0;}
}C[N];
bool cmp(circle a,circle b){return a.r>b.r;}
bool CinC(circle a, circle b){
   LD dis=getdis(a.o,b.o);
   if(dcmp(dis-S(a.r+b.r))>0)
      return 0;
   return 1;
}
int fa[N],used[N],d[N];
int main(){
   int n; scanf("%d",&n);
   C[0].r=inf; fa[0]=-1;//用一个超级圆框住所有圆
   for(int i=1;i<=n;i++) C[i].in();

   sort(C+1,C+1+n,cmp);
   
   for(int i=0;i<=n;i++)
      for(int j=i-1;~j;j--)
         if(CinC(C[j],C[i])) {fa[i]=j;break;}//圆间的包含关系
   
   int q; scanf("%d",&q);
   
   for(int i=1;i<=q;i++){
   	C[n+1].in1(); C[n+2].in1();
   	for(int j=n+1;j<=n+2;j++)
   		for(int k=j-1;~k;k--)
   			if(CinC(C[k],C[j])) {fa[j]=k;break;}

   	int ans=0,x=n+1,y=n+2;

   	for(int j=0;j<=n+2;j++) used[j]=d[j]=0;

   	while((~fa[x])&&!used[fa[x]]) 
			{d[fa[x]]=ans++;used[fa[x]]=1;x=fa[x];}
		ans=0;
   	while((~fa[y])&&!used[fa[y]]) 
			{used[fa[y]]=1;y=fa[y];ans++;}
   	ans+=d[fa[y]];
   //类似于求树上两点距离
   	printf("%d\n",ans);
   }
   return 0;
}

问题是在一些输出0的点输出1