题面
在 Byteland 的首都，有一个以围墙包裹的矩形公园，其中以圆形表示游客和树。
公园里有四个入口，分别在四个角落（
1
,
2
,
3
,
4
1, 2, 3, 4
1,2,3,4 分别对应左下、右下、左上、右上）。游客只能从入口进出。
游客可以在他们与公园的两邻边相切的时候进出对应的出口。游客可以在公园里自由活动但不允许与树相交（可以刚好相切）。
你的任务是为每个游客计算，给定他们进入公园的入口，他们可以从哪个入口离开公园。
题解
如果你没有想到并查集，那估计做不出来。
如果想到了并查集，并且精通并查集套路，那这题就是比较灵活的板题了。
两个圈之间存在一条边，边权为两圆距离，表示直径在这个数之内的旅客可以穿过。
再把四壁抽象成点，分别与每个圈存在边权为圆到壁距离的边，表示直径在这个数之内的旅客可以贴着墙过去。
如果把边权小于旅客直径的边都连上，那么旅客能否到达目的地就只取决于四壁之间的连通关系了。简单讨论一下完事。
我们不能每个旅客都现场连边，所以有两种方法，第一种是离线，第二种是预处理，然后在线判断：
预处理出四面墙壁两两连通之前，能通过的最大圆直径，我们可以把边从小到大排序，依次加入，在每对墙壁第一次连通时，记录下当前最大的边权，就是能通过的最大圆直径了。
时间复杂度
O
(
n
2
log
n
)
O(n^2\log n)
O(n2logn) 。
CODE
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 2005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define SI(x) set<x>::iterator
#define BI bitset<MAXN>
#define eps (1e-4)
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x) return ;
putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
if(!x) putchar('0');
else if(x < 0) putchar('-'),putpos(-x);
else putpos(x);
}
const int MOD = 1000000007;
int n,m,s,o,k;
int ox[MAXN],oy[MAXN];
DB rr[MAXN];
int U,D,L,R,uy,rx;
DB dis(int x,int y,int a,int b) {
return sqrt((x-a)*1.0*(x-a) + (y-b)*1.0*(y-b));
}
struct it{
int u,v;
DB w;it(){u=v=0;w=0.0;}
it(int U,int V,DB W){u=U;v=V;w=W;}
}e[MAXN*MAXN];
bool cmp(it a,it b) {return a.w < b.w;}
int fa[MAXN];
int findf(int x) {return x==fa[x] ? x:(fa[x]=findf(fa[x]));}
void unionSet(int a,int b) {fa[findf(a)] = findf(b);}
DB le[5][5];
bool OK(int x,int y) {return findf(x) != findf(y);}
int main() {
n = read();m = read();
rx = read();uy = read();
U = n+1;D = n+2;L = n+3;R = n+4;
for(int i = 1;i <= n+4;i ++) fa[i] = i;
int cn = 0;
for(int i = 1;i <= n;i ++) {
ox[i] = read();oy[i] = read();
rr[i] = (DB)read();
for(int j = 1;j < i;j ++) {
e[++ cn] = it(j,i,dis(ox[i],oy[i],ox[j],oy[j])-rr[i]-rr[j]);
}
e[++ cn] = it(i,U,(DB)uy-oy[i]-rr[i]);
e[++ cn] = it(i,D,(DB)oy[i]-rr[i]);
e[++ cn] = it(i,L,(DB)ox[i]-rr[i]);
e[++ cn] = it(i,R,(DB)rx-ox[i]-rr[i]);
}
sort(e + 1,e + 1 + cn,cmp);
for(int i = 1;i <= 4;i ++) {
for(int j = 1;j <= 4;j ++) {
le[i][j] = -1.0;
}
}
for(int i = 1;i <= cn;i ++) {
s = e[i].u,o = e[i].v;
DB nw = e[i].w;
if(OK(D,U) && OK(D,L) && OK(D,R)) le[1][2] = le[2][1] = nw;
if(OK(L,U) && OK(L,D) && OK(L,R)) le[1][4] = le[4][1] = nw;
if(OK(L,R) && OK(U,D) && OK(U,R) && OK(L,D)) le[1][3] = le[3][1] = nw;
if(OK(L,U) && OK(L,R) && OK(D,U) && OK(D,R)) le[2][4] = le[4][2] = nw;
if(OK(R,U) && OK(R,L) && OK(R,D)) le[2][3] = le[3][2] = nw;
if(OK(U,L) && OK(U,D) && OK(U,R)) le[3][4] = le[4][3] = nw;
if(findf(s) != findf(o)) {
unionSet(s,o);
}
}
for(int i = 1;i <= m;i ++) {
k = read()*2; s = read();
for(int j = 1;j <= 4;j ++) {
if(le[s][j]+eps >= (DB)k || j == s) {
putchar('0'+j);
}
}ENDL;
}
return 0;
}
