题目分析
　　把平面上每一个区域看作一个结点，最外层没有边界的区域也看作一个结点。如果一个区域刚好被另外一个区域直接包含，则连边。构成的图上做最短路径即可以得到40~60的分数。
　　又发现，上述得到的图是树结构的，在树上预处理好任意两点的最近公共祖先，之后的询问可以线形完成，这便可以得到满分。

/*
标解是这样的：
题目分析
把平面上每一个区域看作一个结点，最外层没有边界的区域也看作一个结点。
如果一个区域刚好被另外一个区域直接包含，则连边。构成的图上做最短路径即可以得到40~60的分数。
又发现，上述得到的图是树结构的，在树上预处理好任意两点的最近公共祖先，之后的询问可以线形完成，
这便可以得到满分。
但是其实可以有更简单的做法
先判断两个人在任意一个圆的圆内还是圆外，如果一个人在圆内，一个人在圆外，
那么必须破坏一个圆，复杂度为N*Q Orz
这样做就很水了 因为考虑到
如果直接返回圆心和该点的欧几里德距离
那么就又设计到了浮点数的问题了 QAQ我太弱所以最讨厌浮点数什么的
所以我们可以直接保留平方就好
因为都是正数嘛~比平方和比自己都是等效的
再运用异或   用两个bool值表示是否在某个圆外
只有异或值为真才要拆了一堵墙
所以这样就可以直接解决了QWQ
*/
#pragma GCC optimize("O2")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const long long MAXN=8010;
struct node
{
    long long x,y,r,s;
}p[MAXN];
int n;
int q;
long long ans;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].r);
        p[i].s=p[i].r*p[i].r;
    }
    cin>>q;
    while(q--)
    {
        ans=0;
        long long a,b,c,d;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        for(int i=1;i<=n;i++)
        {
            long long way1=(a-p[i].x)*(a-p[i].x)+(b-p[i].y)*(b-p[i].y);
            long long way2=(c-p[i].x)*(c-p[i].x)+(d-p[i].y)*(d-p[i].y);
            bool f1=false,f2=false;
            if(way1>=p[i].s)
                f1=true;
            if(way2>=p[i].s)
                f2=true;
            if(f1^f2)
                ans++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
     

假如这题全wa的话，小心关于包含的判断，因为这题数据似乎有相切的情况存在！

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
int x[8004],y[8004],r[8004],a,b,c,d,n,q,sum[8004];
int judge(int xx,int yy,int x0,int y0,int r)
{
if( ((xx-x0)*(xx-x0)+(yy-y0)*(yy-y0))<r*r)
return 1;
return 0;
}
int main()
{
int i,jd1,jd2,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i]>>r[i];
cin>>q;
for(i=1;i<=q;i++)
{
cin>>a>>b>>c>>d;
for(j=1;j<=n;j++)
{
jd1=judge(a,b,x[j],y[j],r[j]);
jd2=judge(c,d,x[j],y[j],r[j]);
//cout<<jd1<<" "<<jd2<<endl;
if(jd1!=jd2)
sum[i]++;
}
}
for(i=1;i<=q;i++)
cout<<sum[i]<<endl;
return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
int x[8004],y[8004],r[8004],a,b,c,d,n,q,sum[8004];
int judge(int xx,int yy,int x0,int y0,int r)
{
if( ((xx-x0)*(xx-x0)+(yy-y0)*(yy-y0))<r*r)
return 1;
return 0;
}
int main()
{
int i,jd1,jd2,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i]>>r[i];
cin>>q;
for(i=1;i<=q;i++)
{
cin>>a>>b>>c>>d;
for(j=1;j<=n;j++)
{
jd1=judge(a,b,x[j],y[j],r[j]);
jd2=judge(c,d,x[j],y[j],r[j]);
//cout<<jd1<<" "<<jd2<<endl;
if(jd1!=jd2)
sum[i]++;
}
}
for(i=1;i<=q;i++)
cout<<sum[i]<<endl;
return 0;
}

先上代码
```c++
#include <bits/stdc++.h>
using namespace std;

int fa[8005], n, q;
int depth[8005];
typedef unsigned long ll;
ll x[8005], y[8005], r[8005];

inline ll dispow(int i, int j)
{
return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

inline bool inside(int i, int j) // i 在 j 内?
{
return r[i] < r[j] && dispow(i, j) <= r[j]*r[j];
}

inline bool inside(ll a, ll b, int j)// (a, b)在j内
{
return (a-x[j])*(a-x[j])+(b-y[j])*(b-y[j]) <= r[j]*r[j];
}

inline int dfs(int i)
{
if (i == n) return depth[i] = 0;
if (depth[i] != -1) return depth[i];
return depth[i] = dfs(fa[i])+1;
}

inline int LCA(int i, int j)
{
while (i != j) {
if (depth[i] >= depth[j]) i = fa[i];
else j = fa[j];
}
return i;
}

int main()
{
memset(depth, -1, sizeof depth);
scanf("%d", &n);
for (register int i = 1; i <= n; i++)
scanf("%ld%ld%ld", &x[i], &y[i], &r[i]);
x[++n] = 0;
y[n] = 0;
r[n] = 10000000000l;
for (register int i = 1; i <= n; i++) {
register int cho = n;
for (register int j = 1; j <= n; j++)
if (j != i && inside(i, j) && inside(j, cho))
cho = j;
fa[i] = cho;
}
//cin.get();
for (int i = 1; i <= n; i++)
depth[i] = dfs(i);
int q;
ll a, b, c, d;
scanf("%d", &q);
for (register int i = 1; i <= q; i++) {
scanf("%ld%ld%ld%ld", &a, &b, &c, &d);
register int choa = n, chob = n;
for (register int j = 1; j <= n; j++) {
if (inside(a, b, j) && inside(j, choa)) choa = j;
if (inside(c, d, j) && inside(j, chob)) chob = j;
}
int lca = LCA(choa, chob);
//cout << choa << " " << chob << " " << lca << endl;
printf("%d\n", depth[choa]+depth[chob]-depth[lca]-depth[lca]);
}
return 0;
}
```
一眼便可以看出是很裸的LCA，而且数据范围小，暴力即可AC。
唯一不爽的是有点卡常数，改成longint就可以AC

先判断两个人在任意一个圆的圆内还是圆外，如果一个人在圆内，一个人在圆外，那么必须破坏一个圆，复杂度为N*Q，刚开始时用int64被卡常，换成longint就过了

var n,i,i1,ans,q:longint;
a,b,c,d:longint;
x,y,r:array[0..10010] of longint;
b1,b2:boolean;
begin
read(n);
for i:=1 to n do
read(x[i],y[i],r[i]);
read(q);
for i1:=1 to q do
begin
read(a,b);
read(c,d);
ans:=0;
for i:=1 to n do
begin
b1:=false;
b2:=false;
if sqr(a-x[i])+sqr(b-y[i])<r[i]*r[i] then b1:=true;
if sqr(c-x[i])+sqr(d-y[i])<r[i]*r[i] then b2:=true;
if (b1<>b2) then inc(ans);
end;
writeln(ans);
end;
end.

幸亏评测机跑得快，否则我的做法会被卡时间...

把圆形看作节点。若A是所有包含B的圆中最小的，那么连一条边B->A。显然建出来的是一棵树，复杂度为O(n^2)。为了使运行效率更高，可以在建树之前把圆形按照半径进行递增排序，这样找到第一个包含B的圆就是A，于是可以break掉。

询问时，先找到点处在哪个圆内，然后找LCA。不想写倍增，偷懒用了一个线性LCA算法也能过。具体做法是：对于LCA(a,b)，由a、b点一直上溯到根，找到2条路径最早的交点。

int LCA(int a, int b){
//END == -1
memset(step, 0, sizeof(step));
memset(used, 0, sizeof(used));
while(a != END){
used[a] = 1;
if(father[a] != END)
step[father[a]] = step[a]+1;
a = father[a];
}
while(!used[b] && b != END){
step[father[b]] += step[b]+1;
b = father[b];
}
return step[b];
}

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*-  */
/*
 * main.cc
 * Copyright (C) 2016 zhangz <sharedocus@126.com>
 * 
 */
#pragma GCC optimize("O2")
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<algorithm>
#include<cmath>
using namespace std;
int x[8005],y[8005],r[8005];
long long r2[8005];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){scanf("%d%d%d",&x[i],&y[i],&r[i]);r2[i]=(long long)r[i]*r[i];}
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);int cnt=0;
        for(int i=0;i<n;i++)
        {
            bool ina,inb;
            ina=inb=false;
            long long deltax=a-x[i];
            long long deltay=b-y[i];
            if(deltax*deltax+deltay*deltay<=r2[i])ina=true;
            deltax=(long long)c-x[i];
            deltay=(long long)d-y[i];
            if(deltax*deltax+deltay*deltay<=r2[i])inb=true;
            if(ina ^ inb)cnt++;
        }
        printf("%d\n",cnt);
    }
}

O(NQ) 700ms+

随便暴力一下就A了 看到题解才发现好迷啊
我是 N*Q的 每次看看是否需要穿过某个圆
就是看看是不是同在圆内圆外或一内一外 后者+1

这样有错误吗>>?

@doc

数据弱，暴力即可......

其实......我并没用LCA，就很迷地A掉了 = = ......先预处理出一棵树，然后每次都dfs去找点的位置然后返回得到答案，居然就过了......可能长得比较帅吧

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
struct wall{
long long x,y,r;
bool operator < (const wall &a) const {
return r>a.r;
}
} w[8005];
struct edge{
int next,to;
} e[16005];
int n,q,ecnt=0,head[8005];
int a,b,c,d;
inline void add(int u,int v) {
e[++ecnt].to=v;
e[ecnt].next=head[u];
head[u]=ecnt;
return;
}
inline long long power(long long x) {
return x*x;
}
inline bool isin(int a,int b) {
return (power(w[a].r) >= power(w[a].x-w[b].x)+power(w[a].y-w[b].y));
}
void init() {
sort(w+1,w+n+1);
memset(head,-1,sizeof(head));
for (int i=1;i<=n;i++) {
int find=0;
for (int j=i-1;j>0;j--) {
if (isin(i,j)) {
find=j;
break;
}
}
add(find,i);
}
return;
}
inline bool paisin(int x) {
return (power(w[x].r) >= power(w[x].x-a)+power(w[x].y-b));
}
inline bool pbisin(int x) {
return (power(w[x].r) >= power(w[x].x-c)+power(w[x].y-d));
}
int dfs(int x) {
bool ain=paisin(x),bin=pbisin(x);
if (x==0)
ain=bin=1;
if (!ain && !bin)
return 0;
int ans=0;
for (int now=head[x];now!=-1;now=e[now].next) {
ans+=dfs(e[now].to);
}
if (ain && bin)
return ans;
return ans+1;
}
int main() {
scanf("%d",&n);
if (n==0) {
scanf("%d",&q);
for (int i=1;i<=q;i++)
printf("0\n");
return 0;
}
for (int i=1;i<=n;i++)
scanf("%lld%lld%lld",&w[i].x,&w[i].y,&w[i].r);
init();
scanf("%d",&q);
for (int i=1;i<=q;i++) {
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",dfs(0));
}
return 0;
}

#include<stdio.h>//垃圾，高精度都不需要，int就够了
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
int x[8004],y[8004],r[8004],a,b,c,d,n,q,sum[8004];
int judge(int xx,int yy,int x0,int y0,int r)
{
if( ((xx-x0)*(xx-x0)+(yy-y0)*(yy-y0))<r*r)
return 1;
return 0;
}
int main()
{
int i,jd1,jd2,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i]>>r[i];
cin>>q;
for(i=1;i<=q;i++)
{
cin>>a>>b>>c>>d;
for(j=1;j<=n;j++)
{
jd1=judge(a,b,x[j],y[j],r[j]);
jd2=judge(c,d,x[j],y[j],r[j]);
//cout<<jd1<<" "<<jd2<<endl;
if(jd1!=jd2)
sum[i]++;
}
}
for(i=1;i<=q;i++)
cout<<sum[i]<<endl;
return 0;
}