Back to : algorithms
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();
    }
}