RT
//#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include #define itn int #define nit int #define ll long long #define ms multiset #define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) #define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i) #define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define re register #define ri re int #define x first #define y second #define il inline #define cp complex #define pii pair //#pra gma G CC opti mize(3) using namespace std; using std::bitset; //using namespace __gnu_pbds; const double Pi=acos(-1); inline int read() { int x=0; bool fu=0; char ch=0; while(ch>'9'||ch<'0') { ch=getchar(); if(ch=='-')fu=1; } while(ch='0') x=(x*10-48+ch),ch=getchar(); return fu?-x:x; } int n,f[100002],dp[100002],fa[100002][22],q,t1,t2,t3; long double r[100002],now,eps=1e-9; pii ct[100002]; vectorc[100002]; struct node{ int pos; bool tp; inline double getx(){ if(tp)return sqrt(max(0.0l,r[pos]*r[pos]-(now-ct[pos].y)*(now-ct[pos].y)))+ct[pos].x+eps; else return -sqrt(max(0.0l,r[pos]*r[pos]-(now-ct[pos].y)*(now-ct[pos].y)))+ct[pos].x-eps; }friend bool operator<(node a,node b){ return a.getx()<b.getx(); } }temp; pairadd[100002],mns[100002]; inline bool cmp(paira,pairb){ return a.first<b.first; }inline void dfs(int pos){ dp[pos]=dp[f[pos]]+1; fa[pos][0]=f[pos]; F(i,1,20)fa[pos][i]=fa[fa[pos][i-1]][i-1]; F(i,0,c[pos].size()-1)dfs(c[pos][i]); }inline int lca(int x,int y){ while(dp[x]>dp[y]){ UF(i,20,0){ if(dp[fa[x][i]]>=dp[y])x=fa[x][i]; } }while(dp[x]<dp[y]){ UF(i,20,0){ if(dp[fa[y][i]]>=dp[x])y=fa[y][i]; } }if(x==y)return x; UF(i,20,0){ if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; }return f[x]; } sets; int main(){freopen("D.in","r",stdin); ct[0]=make_pair(0.0,0.0); r[0]=LLONG_MAX; cin>>n; F(i,1,n){ ct[i]=make_pair((double)read(),(double)read()); r[i]=read(); add[i]=make_pair(ct[i].second-r[i],i); mns[i]=make_pair(ct[i].second+r[i],i); }sort(add+1,add+n+1,cmp),sort(mns+1,mns+n+1,cmp); int i=1,j=1; add[n+1].first=INT_MAX; mns[n+1].first=INT_MAX; s.insert((node){0,0}); s.insert((node){0,1}); F(iakioi,1,n+n){//cout<<s.size()<<endl; if(add[i].first<=mns[j].first){ now=add[i].first; s.insert((node){add[i].second,0}); s.insert((node){add[i].second,1}); temp=*s.upper_bound((node){add[i].second,1}); if(temp.tp){ f[add[i].second]=temp.pos; c[temp.pos].push_back(add[i].second); }else{/*cout<<f[temp.pos]<<' '<<add[i].second<<endl;*/ f[add[i].second]=f[temp.pos]; c[f[temp.pos]].push_back(add[i].second); }i++; }else{ now=mns[j].first; s.erase((node){mns[j].second,0}); s.erase((node){mns[j].second,1}); j++; } }dfs(0); cin>>q; while(q--){ t1=read(),t2=read(); if(t1==t2){ printf("0\n"); continue; } t3=lca(t1,t2); if(t3==t1||t3==t2){ printf("%d\n",int(abs(dp[t1]-dp[t2])-1)); continue; }printf("%d\n",dp[t1]-dp[t3]+dp[t2]-dp[t3]-2); }/*F(i,1,n)cout<<f[i]<<' ';*/ return 0; }
全部评论
(2) 回帖