$$\color{Purple}{kuangbin题解目录}$$
描述
一个二维平面中放着 $n$ 台电脑。
电脑编号 $1 \\sim n$。
每台电脑的具体位置已知。
初始时,所有电脑都是关机状态。
两台电脑可以直接通信当且仅当两台电脑都处于开机状态,并且两电脑之间距离不超过 $d$。
电脑之间还可以通过中介电脑实现间接通信。
例如,电脑 $A$ 既可以与电脑 $B$ 实现直接通信,也可以与电脑 $C$ 实现直接通信,那么电脑 $B$ 和电脑 $C$ 就可以借助电脑 $A$ 实现间接通信。
现在,要按顺序进行若干个操作,操作共分为两种:
O p
,将电脑 $p$ 开机。S p q
,询问电脑 $p$ 和电脑 $q$ 之间能否实现通信。
输入格式
第一行包含两个整数 $n,d$。
接下来 $n$ 行,每行包含两个整数 $x_i,y_i$,表示一台电脑的位置坐标。
接下来若干行,每行包含一个操作命令,格式入题面所述。
输出格式
对于每个询问指令,输出一行答案,如果可以实现通信,则输出 SUCCESS
,否则输出 FAIL
。
数据范围
$1 \\le n \\le 1001$,
$0 \\le d \\le 20000$,
$0 \\le x_i,y_i \\le 10000$,
$1 \\le p,q \\le n$,$q \\neq p$
最多包含 $3 \\times 10^5$ 个操作指令。
输入样例:
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
输出样例:
FAIL
SUCCESS
思路
并查集
问题,在查询
时,若两个点在同一集合内,说明两点之间建立连接;- 在
插入
一个点(开机)时,将其与其他已开机的点并且与该点的距离不超过$d$,进行并查集的合并
;- 在距离的处理中可提前初始化任意两点之间的距离,不至于每次都去求两点之间的距离
代码
不预处理两点间距离
// Problem: 无线网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4269/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-09 23:57:13
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1010
using namespace std;
typedef long long ll;
int n,d;
int fa[MAXN],vis[MAXN];
struct Point{
int x;
int y;
}s[MAXN];
double get_dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(int num)
{
for(int i=1;i<=num;i++)
fa[i]=i;
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> d;
init(n);
for(int i=1;i<=n;i++)
cin >> s[i].x >> s[i].y;
char op;
while(cin >> op)
{
if(op=='S')
{
int a,b;
cin >> a >> b;
int fx=find(a),fy=find(b);
if(fx==fy)
cout << "SUCCESS" << endl;
else cout << "FAIL" << endl;
}
else if(op=='O')
{
int id;
cin >> id;
vis[id]=1;
for(int i=1;i<=n;i++)
{
if(i==id)
continue;
else if(vis[i]==1&&get_dist(s[i],s[id])<=d)
{
int fx=find(id),fy=find(i);
fa[fx]=fy;
}
}
}
}
return 0;
}
预处理两点间距离
// Problem: 无线网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4269/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-09 23:57:13
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1010
using namespace std;
typedef long long ll;
int n,d;
int fa[MAXN],vis[MAXN];
struct Point{
int x;
int y;
}s[MAXN];
double dist[MAXN][MAXN];
double get_dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(int num)
{
for(int i=1;i<=num;i++)
fa[i]=i;
}
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> d;
init(n);
for(int i=1;i<=n;i++)
cin >> s[i].x >> s[i].y;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
dist[i][j]=dist[j][i]=get_dist(s[i],s[j]);
char op;
while(cin >> op)
{
if(op=='S')
{
int a,b;
cin >> a >> b;
int fx=find(a),fy=find(b);
if(fx==fy)
cout << "SUCCESS" << endl;
else cout << "FAIL" << endl;
}
else if(op=='O')
{
int id;
cin >> id;
vis[id]=1;
for(int i=1;i<=n;i++)
{
if(i==id)
continue;
else if(vis[i]==1&&dist[i][id]<=d)
{
int fx=find(id),fy=find(i);
fa[fx]=fy;
}
}
}
}
return 0;
}