Wonseok Shin | BOJ 9373, ICPC-BAPC 2013 복도 뚫기(Getting Through)

Contents

풀이
코드

풀이

반지름 $r_i$인 원을 커버하는 센서 들이 주어진다. 이때 최대한의 반지름 $x$를 가진 원형 로봇을 보내서, 이 센서들에 하나도 걸리지 않고 통과해야 한다.

벽과 각 센서를 모두 정점으로 생각하고, 각 센서들 (벽을 포함) 간의 거리를 길이로 갖는 간선으로 이들 모두를 잇자. 이제, 어떤 경로가 양쪽 벽 정점을 잇는다고 생각하자.

양쪽 벽을 잇는 경로는 우리가 로봇으로 진행할 경로와 반드시 겹친다. 따라서, 벽을 잇는 경로 P는 우리가 만들 수 있는 로봇 직경의 bound를 제공한다. 이를 역으로 생각하면, 벽을 잇는 임의의 경로 P를 통과할 수 있는 직경의 로봇을 만들어야 한다는 것이다.

따라서, 두 벽을 잇는 임의의 경로 중, 간선의 최댓값이 가장 작은 경로를 찾아야 한다. 최댓값 인 이유는 로봇은 항상 최선을 다해 앞으로 나가려고 하므로, 임의의 경로 중 최댓값이 가장 작은 경로를 지날 수 있다면 모든 경로를 지날 수 있기 때문이다. 이를 잘 생각해 보면, MST를 만드는 것처럼 간선들을 추가하다가, 양쪽 벽이 합쳐지는 순간 멈추면 주어진 조건의 경로를 찾을 수 있음을 안다.

코드

음수 길이의 간선을 만들지 않도록 주의하자. 원이 겹칠때 정점을 아예 합쳐줘도 되기는 하는데..굳이?

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

struct pt
{
    double x, y, r;
};

double dt(pt &a, pt &b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

struct edge
{
    int u, v;
    double w;
    bool operator<(const edge &o)
    {
        return w < o.w;
    }
};
vector <edge> elist;
int SC = 1005, SK = 1006;

struct DSU
{
#define V 1010
    int par[V], sz[V];
    DSU(){init(V);}
    void init(int n)
    {
        for (int i = 0; i<n; i++)
            par[i] = i, sz[i] = 1;
    }
    int find(int x)
    {
        return x == par[x] ? x : (par[x] = find(par[x]));
    }
    int getSize(int k){return sz[find(k)];}
    void unite(int x, int y)
    {
        int u=find(x), v=find(y);
        if(u==v) return;
        if(sz[u]>sz[v]) swap(u, v);
        sz[v]+=sz[u];
        sz[u] = 0;
        par[u] = par[v];
    }
} D;

pt pts[1010];
void solve()
{
    D.init(V);
    double W; cin >> W;
    int n; cin >> n;
    if (n == 0)
    {
        cout << fixed << setprecision(20) << W / 2 << '\n';
        return;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> pts[i].x >> pts[i].y >> pts[i].r;
        elist.push_back({SC, i, max(0.0, pts[i].x - pts[i].r)});
        elist.push_back({SK, i, max(0.0, W - pts[i].x - pts[i].r)});
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            elist.push_back({i, j, max(0.0, dt(pts[i], pts[j]) - pts[i].r - pts[j].r)});
    sort(all(elist));
    double ans = 0;
    for (auto e : elist)
    {
        D.unite(e.u, e.v);
        if (D.find(SK) == D.find(SC))
        {
            ans = e.w / 2;
            break;
        }
    }
    cout << fixed << setprecision(20) << ans << '\n';
}

int32_t main()
{
    usecppio
    int T; cin >> T;
    while(T--)
    {
        elist.clear();
        solve();
    }
}