Description
给定平面上 $n$ 个圆，这些圆之间只有包含和分离两种关系(不存在相切的情况)。 定义两个圆之间的距离是从圆 $A$ 到圆 $B$ 经过的圆弧的最小个数，但是不包括 圆 $A$ 和圆 $B$ 的圆弧。两个圆之间的路径不一定只是走直线，还可以存在绕弯 的情况。 对于上述情况，从绿色圆到橙色圆的距离是 $0$，而从红色圆到橙色圆的距离是 $1$。 给出 $q$ 个询问，每个询问的格式形如 $u,v$，对于每个询问，都需要回答第 $u$ 个 圆到第 $v$ 个圆之间的最短距离。
Solution
题中给出数个不相交或相切的圆，问从一个圆到另一个圆最少走过几个圆
可以想到圆的包含和相离可以视为树上的结构：圆A包含圆B就是A是B的父节点，圆A与圆B相离就是A，B为兄弟节点，那么两圆之间距离就可以用
LCA求出
用扫描线维护每个圆的左端点和右端点，当扫到一个入点时判断它上方的圆弧，如果是下半弧则与该圆相离，如果是上半弧则被该圆包含，那么就可以把深度和父节点更新
最后倍增求LCA，要分LCA是否与两个圆重合两类讨论答案（果然不能一概而论）
#include<algorithm> #include<iostream> #include<vector> #include<cstdio> #include<cmath> #include<set> using namespace std; int n,q,X[100005],Y[100005],R[100005],tot,nowx,dep[100005],fa[100005],f[100005][20]; struct Eve { double x; int id,typ; bool operator < (const Eve &z)const { return x<z.x; } }eve[200005]; vector<int>ve[100005]; struct Node { int id,typ; double loc()const { double temp=sqrt(1.0*R[this->id]*R[this->id]-1.0*(X[this->id]-nowx)*(X[this->id]-nowx)+1e-8); return (this->typ==1)?Y[this->id]-temp:Y[this->id]+temp; } }; bool operator < (Node y,Node z) { return y.loc()<z.loc(); } set<Node>s; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } void dfs(int k) { f[k][0]=fa[k]; for(int i=1;i<=19;i++) f[k][i]=f[f[k][i-1]][i-1]; for(int v:ve[k]) dfs(v); } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=19;~i;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i]; if(u==v) return u; for(int i=19;~i;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; } int dis(int u,int v) { if(u==v) return 0; int d=lca(u,v); return (u!=d&&v!=d)?dep[u]+dep[v]-2*dep[d]-2:dep[u]+dep[v]-2*dep[d]-1; } int main() { n=read(); for(int i=1;i<=n;i++) X[i]=read(),Y[i]=read(),R[i]=read(); for(int i=1;i<=n;i++) eve[++tot]=(Eve){X[i]-R[i]+1e-8,i,1},eve[++tot]=(Eve){X[i]+R[i]-1e-8,i,-1}; sort(eve+1,eve+tot+1); for(int i=1;i<=tot;i++) { nowx=eve[i].x; if(eve[i].typ==-1) s.erase((Node){eve[i].id,1}),s.erase((Node){eve[i].id,2}); else { auto temp=s.upper_bound((Node){eve[i].id,1}); if(temp==s.end()) dep[eve[i].id]=1; else { Node a=*temp; if(a.typ==1) dep[eve[i].id]=dep[a.id],fa[eve[i].id]=fa[a.id]; else dep[eve[i].id]=dep[a.id]+1,fa[eve[i].id]=a.id; } s.insert((Node){eve[i].id,1}),s.insert((Node){eve[i].id,2}); } } for(int i=1;i<=n;i++) ve[fa[i]].push_back(i); dfs(0); q=read(); for(int i=1;i<=q;i++) { int u=read(),v=read(); printf("%d ",dis(u,v)); } return 0; }