DDOSvoid's Blog

校内赛 T4 扫地机器人

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

简要题意：给定一个长度无限大，宽度为 $m$ 的平面，现在我们依次在平面上加入 $n$ 个点，每加入一个点都需要求一个最小的半径 $r$，使得平面上这些点变成半径为 $r$ 的圆后，这些圆的并将平面封住，即无法从平面最左侧走到最右侧

$n\le 2000$

Solution

我们考虑如果机器人的半径是 $r$ 会发生什么

以每个家具为圆心画半径为 $r$ 的圆，机器人的圆心不能在这个园内

那么我们考虑如果家具的圆将上下封住机器人就没法走了

所以我们以家具之间的距离为边的长度建图，然后跑最小生成树即可

注意到要求 $n$ 次最小生成树，且每次需要加 $O(n)$ 条边

但实际上我们每次只需要保留上一棵树的树边，与新加的边一起跑 $kruskal$ 即可

时间复杂度 $O(n^2\log n)$

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 2510
#define db double
#define cn const node
#define cE const Edge
using namespace std;

int n, m, s, t; 

struct node {
    int x, y;
} a[maxn];

struct Edge {
    int fr, to; db w;

    friend bool operator < (cE &u, cE &v) { return u.w < v.w; } 
} e[maxn * 2]; int c1;
inline void add_edge(int u, int v, db w) {
    e[++c1].fr = u; e[c1].to = v; e[c1].w = w;
}

inline db S(db x) { return x * x; } 

inline db dis(cn &u, cn &v) { 
    return sqrt(S(u.x - v.x) + S(u.y - v.y));
}

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int main() {
    cin >> n >> m; s = n + 1; t = n + 2; 
    for (int o = 1; o <= n; ++o) {
        cin >> a[o].x >> a[o].y; 
        add_edge(s, o, a[o].y); add_edge(o, t, m - a[o].y); 
        for (int i = 1; i < o; ++i) add_edge(o, i, dis(a[o], a[i]));
        sort(e + 1, e + c1 + 1); init_fa(n + 2); int s = 0; db ans = 0; 
        for (int i = 1; i <= c1; ++i) {
            int u = e[i].fr, v = e[i].to, fu, fv; db w = e[i].w;
            if ((fu = find(u)) == (fv = find(v))) continue ; fa[fu] = fv;
            if (find(s) == find(t) && !ans) ans = w;
            if (++s == o + 1) { c1 = i; break; } 
        }
        cout << (int) (ans / 2) << endl; 
    }       
    return 0;
}