乔斯编程——P3283 通信救援

说明

众所周知，在同一平面内到定点的距离等于定长的点的集合叫做圆。这个定点叫做圆的圆心，定长即圆的半径。
同时用圆心的坐标和圆的半径，就可以确定圆在平面内的位置，在本题当中，我们根据圆在平面覆盖的区域来描述信号站的有效通信范围。
某一天，A 城因暴雨天气，导致 n 个信号站通信中断，第 ii 个信号站的坐标为 (xi,yi) ，同时以(ri)为圆的半径，这个圆覆盖的区域代表第 i 个信号站的有效通信范围。

设置 di,j 为两个信号站圆心之间的直线距离，[公式链接]

两点间距离公式_百度百科

当第 i 个信号站恢复通信时，根据第 j 个信号站与其的距离分类讨论：

1. 当 di,j <= (ri+rj) 时，由于通信共享，第 j 个信号站也恢复通信作用。
2. 当 di,j > (ri+rj) 时，由于距离较远，第 j 个信号站无法恢复通信作用。
一位技术工程师可以前往一个信号站救援通信，问最少需要多少位技术工程师可以恢复 A 城的所有通信网络？

样例解释如图所示：第一位工程师恢复紫色区域的信号站，第二位工程师恢复黑色区域的信号站时，由于通信共享红色和蓝色区域依次恢复通信。

输入格式

第一行一个整数 n，表示 A 城的 n 个信号站通信中断。
接下来 n 行，每行三个整数 xi,yi,ri 表示第 i 个信号站的坐标和通信范围。

输出格式

输出一个整数，表示最少的人数可以恢复 A 城的通信。

样例

输入数据 1

输出数据 1

提示

【数据范围】

对于30%的数据：1≤n≤20，−100≤xi,yi≤ 100，1≤ri≤100。

对于100%的数据保证：1≤n≤5000，−1000≤xi,yi≤ 1000，1≤ri≤100。

解题思路

对于这题我们可以通过题面中的图来把它理解为一个连通块问题，再通过深搜求有几个连通块即可。

AC代码

#include<iostream>
#include<cmath>
using namespace std;
long long vis[5500], x[5500], y[5500], r[5500];
long long n;
double dis(int _x, int _y)
{return sqrt(abs(x[_x] - x[_y]) * abs(x[_x] - x[_y]) + abs(y[_x] - y[_y]) * abs(y[_x] - y[_y]));
}
void dfs(int x)
{for (int i = 1; i <= n; i++){if (!vis[i] && dis(x, i) <= r[i] + r[x]){vis[i] = 1;dfs(i);}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> x[i] >> y[i] >> r[i];}int cnt = 0;for (int i = 1; i <= n; i++){if (!vis[i]){cnt++;vis[i] = 1;dfs(i);}}cout << cnt;return 0;
}