백준 11096번: UnDetected [C++]

작성일 | In
플래티넘 IV 플래티넘 IV

문제

UnDetected

풀이

$y = 0$인 지점에서 $y = 300$인 지점까지 갈 수 없다는 것은 센서들의 범위가 왼쪽 벽과 오른쪽 벽을 잇고 있다는 것과 동치입니다.

따라서 $1$번 센서부터 분리 집합에서 인접한 센서 혹은 벽과 연결해주면서 불가능할 때 멈추면 답이 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()

struct DisjointSet {
    vector<int> parent;

    DisjointSet(int n) : parent(n) { iota(all(parent), 0); }

    int findParent(int x) {
        if (x != parent[x])
            parent[x] = findParent(parent[x]);
        return parent[x];
    }

    void unionParent(int u, int v) {
        u = findParent(u), v = findParent(v);

        if (u != v)
            parent[v] = u;
    }

    bool isConnected(int u, int v) { return findParent(u) == findParent(v); }
};

struct Circle {
    int x, y, r;

    bool isOverlap(const Circle& c) {
        int dx = x - c.x;
        int dy = y - c.y;
        int rr = r + c.r;

        return dx*dx + dy*dy < rr*rr;
    }
};

Circle circle[222];

constexpr int width = 200;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    int lWall = 0, rWall = N + 1;
    DisjointSet ds(N + 2);

    int answer = 0;
    for (int i = 1; i <= N; i++) {
        auto& [x, y, r] = circle[i];
        cin >> x >> y >> r;

        if (x - r <= 0)
            ds.unionParent(lWall, i);
        if (x + r >= width)
            ds.unionParent(rWall, i);

        for (int j = 1; j < i; j++) {
            if (not circle[i].isOverlap(circle[j]))
                continue;

            ds.unionParent(i, j);
        }

        if (ds.isConnected(lWall, rWall))
            break;
        answer = i;
    }

    cout << answer;

    return 0;
}

백준 11096번: UnDetected [C++]