AtCoder Beginner Contest 259 - D - Circumferences

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400$ points

Problem Statement

You are given $N$ circles on the $xy$-coordinate plane. For each $i = 1, 2, \ldots, N$, the $i$-th circle is centered at $(x_i, y_i)$ and has a radius of $r_i$.

Determine whether it is possible to get from $(s_x, s_y)$ to $(t_x, t_y)$ by only passing through points that lie on the circumference of at least one of the $N$ circles.

Constraints

• $1 \leq N \leq 3000$
• $-10^9 \leq x_i, y_i \leq 10^9$
• $1 \leq r_i \leq 10^9$
• $(s_x, s_y)$ lies on the circumference of at least one of the $N$ circles.
• $(t_x, t_y)$ lies on the circumference of at least one of the $N$ circles.
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

$N$
$s_x$ $s_y$ $t_x$ $t_y$
$x_1$ $y_1$ $r_1$
$x_2$ $y_2$ $r_2$
$\vdots$
$x_N$ $y_N$ $r_N$

Output

If it is possible to get from $(s_x, s_y)$ to $(t_x, t_y)$, print Yes; otherwise, print No. Note that the judge is case-sensitive.

---

Sample Input 1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

Sample Output 1

Yes

Here is one way to get from $(0, -2)$ to $(3, 3)$.

• From $(0, -2)$, pass through the circumference of the $1$-st circle counterclockwise to reach $(1, -\sqrt{3})$.
• From $(1, -\sqrt{3})$, pass through the circumference of the $2$-nd circle clockwise to reach $(2, 2)$.
• From $(2, 2)$, pass through the circumference of the $3$-rd circle counterclockwise to reach $(3, 3)$.

Thus, Yes should be printed.

---

Sample Input 2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

Sample Output 2

No

It is impossible to get from $(0, 1)$ to $(0, 3)$ by only passing through points on the circumference of at least one of the circles, so No should be printed.

题目大意

给你一些圆⚪，以及两个点📍

问你 在只经过圆周⚪的前提下，能否由第一个点📍达到第二个点📍

数据保证两个点都在圆周⚪上

解题思路

本题圆⚪的数量级别为$3000$，$O(n^2)$的复杂度在AtCoder上2秒可以通过。

所以不难想到，我们可以把此题转换为连通图问题：

把一个圆⚪看成一个节点，相交的两个圆⚪之间存在一条路径

很容易在$O(n^2)$的时间内把图构建出来

然后，只需要看两个点📍所在的节点（如果某个点在多个圆⚪上，任取一个作为这个点📍所在的节点即可）是否在一个连通图上

定义圆⚪的数据结构

struct circle {
    ll x, y, r;
    bool used = false;  // 后面在判断连通图的时候会用到
};

判断两个圆⚪是否相交/相切

相交/相切 条件：$R-r \leq 圆心距离 \leq R+r$

严格地说“相切”不属于“相交”。这里感谢@ZZXzzx0_0大佬的指正~

inline bool intersect(int x, int y) {
    ll r = a[x].r;
    ll R = a[y].r;
    if (r > R)
        swap(r, R);
    ll distance2 = (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);
    return (R - r) * (R - r) <= distance2 && distance2 <= (R + r) * (R + r);
}

判断一个点📍是否在一个圆⚪上

// (x, y) 是否在第th个圆⚪上
inline bool onCircle(ll x, ll y, int th) {
    return (x - a[th].x) * (x - a[th].x) + (y - a[th].y) * (y - a[th].y) == a[th].r * a[th].r;
}

是否能从节点x走到节点y

建好图后，假设两个点📍分别在节点$x$和节点$y$上，则只需要判断$x$和$y$是否在一个连通图上即可

bool ifCanGo(int x, int y) {
    // 把从x能到达的所有节点的used标记为true
    queue<int> canGo;
    canGo.push(x);
    a[x].used = true;
    while (canGo.size()) {
        int thisNode = canGo.front();
        canGo.pop();
        for (int &t : ma[thisNode]) {
            if (!a[t].used) {
                canGo.push(t);
                a[t].used = true;
            }
        }
    }
    // 判断y是否被标记了
    return a[y].used;
}

建图

vector<int> ma[3010];  // 存图

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (intersect(i, j)) {
            ma[i].push_back(j);
            ma[j].push_back(i);
        }
    }
}

---

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

// 小心精度误差

// #define Yes {puts("Yes"); return 0;}
// #define No {puts("No"); return 0;}

#define EXIT(x) {puts(#x); return 0;}
#define Yes
#define No

struct circle {
    ll x, y, r;
    bool used = false;  
};

circle a[3010];

inline bool onCircle(ll x, ll y, int th) {
    return (x - a[th].x) * (x - a[th].x) + (y - a[th].y) * (y - a[th].y) == a[th].r * a[th].r;
}

inline bool intersect(int x, int y) {
    ll r = a[x].r;
    ll R = a[y].r;
    if (r > R)
        swap(r, R);
    ll distance2 = (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);
    return (R - r) * (R - r) <= distance2 && distance2 <= (R + r) * (R + r);
}

vector<int> ma[3010];  // 图

bool ifCanGo(int x, int y) {
    queue<int> canGo;
    canGo.push(x);
    a[x].used = true;
    while (canGo.size()) {
        int thisNode = canGo.front();
        canGo.pop();
        for (int &t : ma[thisNode]) {
            if (!a[t].used) {
                canGo.push(t);
                a[t].used = true;
            }
        }
    }
    return a[y].used;
}

int main() {
    int n;
    ll sx, sy, tx, ty;
    cin >> n >> sx >> sy >> tx >> ty;
    int sOnCircle, tOnCircle;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].r;
        if (onCircle(sx, sy, i))
            sOnCircle = i;
        if (onCircle(tx, ty, i))
            tOnCircle = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (intersect(i, j)) {
                ma[i].push_back(j);
                ma[j].push_back(i);
            }
        }
    }
    if (ifCanGo(sOnCircle, tOnCircle)) {
        EXIT(Yes);
    }
    else {
        EXIT(No);
    }
    return 0;
}

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125700650