C++ 圆与圆之间的距离是不能一概而论的
【题目描述】
给定平面上 n 个圆，这些圆之间只有包含和分离两种关系(不存在相切的情况)。
定义两个圆之间的距离是从圆 A 到圆 B 经过的圆弧的最小个数，但是不包括圆 A 和圆 B
的圆弧。两个圆之间的路径不一定只是走直线，还可以存在绕弯的情况。
对于上述情况，从绿色圆到橙色圆的距离是 0，而从红色圆到橙色圆的距离是 1。
给出 q 个询问，每个询问的格式形如 u, v，对于每个询问，都需要回答第 u 个圆到第 v 个圆之间的最短距离。
【输入格式】
接下来n行，每行三个整数xi,yi,ri表示第 i 个圆的圆心与半径。
第 n + 2 行一个整数 q 表示询问的个数。
接下来 q 行，每行两个整数 u, v，表示需要求第 u 个圆到第 v 个圆的最短距离。
【输出格式】
对于每个询问，输出一行一个整数表示答案。
【样例 1 输入】
59 -7 40 -6 4-6 10 19 8 2-1 9 825 32 3【样例 1 输出】
01
CODE
#include #define for1(i,n) for(i=1;i<=(n);i++)using namespace std;typedef long long ll;typedef unsigned long long ull;const int N=100005;int n,q,dep[N],f[N][20],cs[N],cp,b[N],si[N],t[N];struct nd{int x,y,r,id;bool operator<(const nd &n1)const{return y-r<n1.y-n1.r;}bool p(nd &n1){return r+y<n1.y-n1.r;}bool dr(nd &n1){ll dy=(ll)y-n1.y+n1.r,dx=x-n1.x;return dx>=0||(ull)((ll)dx*dx)+(ull)(dy*dy)<(ll)r*r;}bool d(nd &n1){ll dy=(ll)y-n1.y+n1.r,dx=x-n1.x;return (ull)((ll)dx*dx)+(ull)(dy*dy)<(ll)r*r;}}a[N];struct jlis{int h,c,d,u,l,r;}lis[N*20];void blr(int l,int r){lis[l].r=r;lis[r].l=l;}void bdu(int d,int u){lis[u].d=d;lis[d].u=u;}void add(int fr,int x){b[x]=++cp;lis[cp].h=x;blr(cp,lis[fr].r);blr(fr,cp);int cnt=0;while((rand()&1)&&cnt<=19){while(!lis[fr].u) fr=lis[fr].l;fr=lis[fr].u;lis[++cp].h=x;blr(cp,lis[fr].r);blr(fr,cp);bdu(cp-1,cp),lis[cp].c=++cnt;}}void era(int p,bool w){while(lis[p].c) p=lis[p].d;if(w&&!--si[f[lis[p].h][0]]) add(p,f[lis[p].h][0]);while(p) blr(lis[p].l,lis[p].r),p=lis[p].u;}int sov(int x){int p=41;while(1){while(1){int &rh=lis[p].r;if(!lis[rh].h) break;while(a[lis[rh].h].p(a[x])){era(rh,1);if(!lis[rh].h) break;}if(!lis[rh].h||a[lis[rh].h].dr(a[x])) break;p=rh;}if(!lis[p].c) break;p=lis[p].d;}return p;}int lca(int x,int y){int i,xx=x,yy=y;if(dep[x]<dep[y]) swap(x,y);for(i=17;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return dep[xx]+dep[yy]-2*dep[x]-1;for(i=17;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return dep[xx]+dep[yy]-2*dep[x];}int bz(int x,nd &y){if(a[x].d(y)) return x;int i;for(i=17;i>=0;i--) if(f[x][i]&&!a[f[x][i]].d(y)) x=f[x][i];return f[x][0];}int main(){srand(time(0));int i,j,p1,p2,pp1,pp2,fp;si[0]=1e9;cp+=2,blr(cp-1,cp);for1(i,20){cp+=2;lis[cp].c=lis[cp-1].c=i;blr(cp-1,cp);bdu(cp-3,cp-1);bdu(cp-2,cp);}scanf("%d",&n);for1(i,n) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r),a[i].id=i;sort(a+1,a+n+1);for1(i,n){t[a[i].id]=i;p1=sov(i);p2=lis[p1].r;while(lis[p2].h&&a[lis[p2].h].p(a[i])){era(p2,1);p2=lis[p1].r;}pp1=bz(lis[p1].h,a[i]);pp2=bz(lis[p2].h,a[i]);fp=dep[pp1]>dep[pp2]?pp1:pp2;add(p1,i);if(fp&&!si[fp]++) era(b[fp],0);dep[i]=dep[fp]+1;f[i][0]=fp;for1(j,17) f[i][j]=f[f[i][j-1]][j-1];//printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].r,fp);//for1(j,n) printf("si:%d %d\n",j,si[j]);}scanf("%d",&q);for1(i,q){scanf("%d%d",&p1,&p2);printf("%d\n",lca(t[p1],t[p2]));}return 0;}