做题目时因为没有题解，自己调试了半天，于是想把自己的程序分享一下，给后来者参考参考。

进入正题

这道题目运用到 并查集 和 离线
上述算法不清楚不要紧，我们慢慢来。

并查集

并查集从字面意思上来理解，是一种支持合并与查询的数据结构。并查集的合并指的是将两颗有根树合并，查询指的是查询节点的根。

并查集的基本思路是路径压缩，对于任意节点$x$，我们让节点$x$的父指针指向根，根的父指针指向自己，这样查询时便可以一步到位。对于合并，就只需查找根节点，然后将其中一个根的父指针指向另一个根就行了。但是，你可能有疑惑，这样并没有路径压缩呀。其实，路径压缩是在查询时进行的。我们一边查询一边用返回值更新父指针，如代码：

inline int find(int x)                    //查询根节点
{
    if (f[x]==x) return x;                //如果当前节点为根节点，返回本身。
    f[x]=find(f[x]);                      //否则，查询父节点，并将父指针指向根节点。
    return f[x];                          //返回根节点
}

合并的代码就更加简单了：

inline void together(int x,int y)
{
	int r1,r2;
    r1=find(x);r2=find(y);       //查询x、y的根
    if (r1==r2) return ;         //若x、y以在同一棵树中，不合并
    f[r1]=r2;                    //将r1的根置为r2
}

这一题，我们可以用并查集来判断连通情况，如果树与边界相交或树与树相交(相切也算)，合并。最后，判断两边界是否处于同一集合中，若是，则不能通行，否则，能过。但这也仅仅只是判断了相交的情况，一些情况下，即使是两树不相交，它们的距离过小，长得胖的人也过不去。

对与这个情况，一种解决方法是建立$m$个并查集，枚举距离，小于人的直径时，就合并。当这种方法时间复杂度太高。于是，我便想到了第二种方法，离线处理，将人按直径(输入是半径)由小到大排序，距离也按由小到大排序，这样原先无法通过的距离，之后任然无法通过。就不需要重复处理，还可以用一个$last$变量记录上次判断到的距离。

$code:$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2015;
const int MAXM=100015;
const double eps=1e-4;
int n,m,id,last,k;
long long l,r;

struct tree
{
    long long x,y,d;
    
    inline double operator - (struct tree tmp) 
    {
        return sqrt((x-tmp.x)*(x-tmp.x)+(y-tmp.y)*(y-tmp.y))-d-tmp.d;
    }
}t[MAXN];

struct man
{
    long long from,id,d;
    
    inline bool operator < (const man &tmp) const
    {
        return d<tmp.d;
    }
}w[MAXM];

struct cost
{
    long long a,b;double dis;
    
    inline bool operator < (const cost &tmp) const
    {
        return dis<tmp.dis;
    }
}h[MAXN*MAXN];
int f[MAXM];
bool ans[MAXM][5],map[5][5];

inline int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

inline void together(int x,int y)
{
    int r1,r2;
    r1=find(x);r2=find(y);
    if (r1==r2) return ;
    f[r1]=r2;
}

inline void turn_off(int x,int y)
{
    map[x][y]=map[y][x]=false;
}

int main()
{
    cin>>n>>m>>l>>r;
    for (int i=1;i<=n;i++) cin>>t[i].x>>t[i].y>>t[i].d;
    for (int i=1;i<=m;i++) {cin>>w[i].d>>w[i].from;w[i].d*=2;w[i].id=i;}
    for (int i=1;i<=n;i++)
    {
        h[++id]=(cost){i,n+1,(double)t[i].x-t[i].d};
        h[++id]=(cost){i,n+2,(double)t[i].y-t[i].d};
        h[++id]=(cost){i,n+3,(double)l-t[i].x-t[i].d};
        h[++id]=(cost){i,n+4,(double)r-t[i].y-t[i].d};
        for (int j=i+1;j<=n;j++) h[++id]={i,j,fabs(t[i]-t[j])};
    }
    last=1;
    sort(h+1,h+id+1); sort(w+1,w+m+1);
    for (int i=1;i<=4;i++)
        for (int j=1;j<=4;j++) map[i][j]=true;
    for (int i=1;i<=n+10;i++) f[i]=i;
    for (int i=1;i<=m;i++)
    {
        while (last<=id&&h[last].dis+eps<=w[i].d) {together(h[last].a,h[last].b);last++;}
        if (find(n+1)==find(n+3)) turn_off(1,3),turn_off(1,4),turn_off(2,3),turn_off(2,4);
        if (find(n+2)==find(n+4)) turn_off(1,2),turn_off(1,3),turn_off(2,4),turn_off(3,4);
        if (find(n+1)==find(n+2)) turn_off(1,2),turn_off(1,3),turn_off(1,4);
        if (find(n+2)==find(n+3)) turn_off(1,2),turn_off(2,4),turn_off(2,3);
        if (find(n+3)==find(n+4)) turn_off(3,1),turn_off(3,2),turn_off(3,4);
        if (find(n+4)==find(n+1)) turn_off(4,1),turn_off(4,2),turn_off(4,3);
        for (int j=1;j<=4;j++) ans[w[i].id][j]=map[w[i].from][j];
    }
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=4;j++)
            if (ans[i][j]) putchar(j+'0');
        putchar('\n');
    }
    return 0;
}

$Please~give~a~like.~~Thanks~for~reading~my~passage.$

Solution

经典 Trick :

我们发现不同的游客的大小不一样 , 这很麻烦 .

那么想办法 , 把游客的大小转化成树的大小 .

最显然的方法 , 就是对于每个半径为 $r$ 的游客 , 让所有的树的半径加上 $r$ . 如图 .

这样我们就可以把游客看做点了 . 这是后可以判段四个角之间是否联通 . 方法参考普及组难度题目《奶酪》 , 把四条边也都当作一个点 .

当 A 与 B 不能联通有如下 3 种情况 :

对于这道题 , 我们可以考虑离线 . 预处理出任意两棵树 ( 包括边界 ) 中间的路堵上所需的游客直径 . 拿一个指针扫描 , 然后判段连通性即可 . 注意根据题目 , 一个点总是可以到达其起点的 .

关于边界的编号 , 我们可以从最左开始逆时针编为 $n+1 \sim n+4$ , 这样更方便实现 .

code :

const int MAXN=2000+10,MAXM=1e5+10;
struct Query {
	int idx,st,r;	
}qr[MAXM];
struct Union {
	int x,y;
	double r;	
}un[MAXN*MAXN];
inline bool cmp(const Query A,const Query B) {
	return A.r<B.r;	
}
inline bool Cmp(const Union A,const Union B) {
	return A.r<B.r;	
}
int n,m,w,h,ans[MAXM][5],fa[MAXN];
int cnt,x[MAXN],y[MAXN],r[MAXN];
inline int find(const int k) {
	if(fa[k]==k) return k;
	return fa[k]=find(fa[k]);	
}
inline double distance(const double x,const double y,const double X,const double Y) {
	return sqrt((x-X)*(x-X)+(y-Y)*(y-Y));	
}
inline void init(void) {
	for(int i=1;i<=n+4;i++) fa[i]=i;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<i;j++) un[++cnt]=Union{i,j,distance(x[i],y[i],x[j],y[j])-r[i]-r[j]};
		un[++cnt]=Union{i,n+1,x[i]-r[i]};
		un[++cnt]=Union{i,n+2,y[i]-r[i]};
		un[++cnt]=Union{i,n+3,w-x[i]-r[i]};
		un[++cnt]=Union{i,n+4,h-y[i]-r[i]};
	}
	sort(un+1,un+cnt+1,Cmp);
	return ;	
}
inline void Merge(int x,int y) {
    x=find(x),y=find(y),fa[x]=y;
    return ;
}
inline int trapped(const int idx) { //困在拐角出不去
    return find(n+idx)==find(n+idx%4+1);
}
inline int cross_row(void) { //横向
    return find(n+1)==find(n+3);
}
inline int cross_line(void) { //纵向
    return find(n+2)==find(n+4);
}
inline int able_to_reach(const int idx1,const int idx2) {
    if(idx1==idx2) return 1;
	if(trapped(idx1)||trapped(idx2)) return 0;
    if(abs(idx1-idx2)==2) {
        if(cross_line()||cross_row()) return 0;
        return 1;
    }
    if(idx1+idx2==3||idx1+idx2==7) {
        if(cross_line()) return 0;
        return 1;
    }
    if(cross_row()) return 0;
    return 1;
}
signed main() {
	n=read(),m=read(),w=read(),h=read();
	for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),r[i]=read();
	init();
	for(int i=1,st,r;i<=m;i++) r=read(),st=read(),qr[i]=Query{i,st,r};
    sort(qr+1,qr+m+1,cmp);
    int pos=0;
    for(int i=1;i<=m;i++) {
        while(pos<cnt&&un[pos+1].r-2*qr[i].r<=-1e-7) pos++,Merge(un[pos].x,un[pos].y);
        for(int j=1;j<=4;j++) if(able_to_reach(qr[i].st,j)) ans[qr[i].idx][j]=1;
    }
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=4;j++) if(ans[i][j]) printf("%d",j);
        printf("\n");
    }
	return 0;
}

PS :

1. 注意数组大小 .

2. 这种我一眼爆切的题目不大可能是黑题吧 ......