题解
大部分人是用几何性质去枚举的。
标算貌似用了线性求LCA，常数很大的样子。我是暴力建树，然后用了类似于LCA的方法求最长公共路径，然后再求不同的路。
本质上可能是一样的，不过我这个居然更快？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
typedef long long ll;
int n,m,x_1,x_2,y_1,y_2,par[8005],son[8005],bro[8005];
int cx,cy,rec[2][8005],tot[2]={0};
struct C{
int id,x,y,r;
bool operator<(C c){
return r>c.r;
}
};
C cir[8005];
void dfs(int id,int o){
int dx,dy,dr;
for(int i=son[id];i!=-1;i=bro[i]){
dx=cir[i-1].x,dy=cir[i-1].y,dr=cir[i-1].r;
if((cx-dx)*(cx-dx)+(cy-dy)*(cy-dy)<=dr*dr){
rec[o][tot[o]++]=id;
dfs(i,o);
return ;
}
}
rec[o][tot[o]++]=id;
return ;
}
void insert_(int cur,int id){
int dx,dy,dr;
for(int i=son[cur];i!=-1;i=bro[i]){
dx=cir[i-1].x,dy=cir[i-1].y,dr=cir[i-1].r;
if((cx-dx)*(cx-dx)+(cy-dy)*(cy-dy)<=dr*dr){
insert_(i,id);
return ;
}
}
par[id]=cur,bro[id]=son[cur],
son[cur]=id;
}
void init(){
memset(son,-1,sizeof(son));
memset(par,-1,sizeof(par));
memset(bro,-1,sizeof(bro));
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r);
sort(cir,cir+n);
scanf("%d",&m);
//建树
for(i=0;i<n;i++)
cx=cir[i].x,cy=cir[i].y,
insert_(0,i+1);
}
void solve(){
int i,j,lim,ans;
for(i=0;i<m;i++){
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
tot[0]=tot[1]=0;
cx=x_1,cy=y_1,dfs(0,0);
cx=x_2,cy=y_2,dfs(0,1);
lim=min(tot[0],tot[1]);
for(j=0;j<lim;j++)
if(rec[0][j]!=rec[1][j])break;
ans=tot[0]+tot[1]-2*j;
printf("%d\n",ans);
}
}
int main(){
init();
solve();
return 0;
}