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) 回帖