题解 P6505 【Run Away】

· · 题解

P6505 Run Away

题解区给出的都是 Voronoi 图的神仙做法，但这里将介绍一种很玄学但很好写又很快的做法

首先看到最远距离，先进行二分这个距离，这是所有的点扩散成一个个圆，我们只需要判断这些圆是否完全填满了这个矩形，那么如何判断呢

那么很玄学的就来了，我们采用分治的思想，首先一个矩形，先判断它是否可以只被一个圆覆盖，然后判断四个角只要有一个角没被覆盖就不行，如果都被覆盖了，那么递归下去，将大矩形横竖切两刀分成四个小矩形继续判断，当矩形的长度小于精度要求时返回 false

这个看起来很玄学，但实际跑起来飞快，缺点是速度和精度有关，请谨慎使用

代码部分借鉴 Luitaryi

#pragma GCC optimize(3, "inline")
#include <iostream>
#include <cstdio>
#define R register int
using namespace std;
inline int g() {
    R x = 0, f = 1;
    register char s;
    while (!isdigit(s = getchar())) f = s == '-' ? -1 : f;
    do
        x = x * 10 + (s ^ 48);
    while (isdigit(s = getchar()));
    return x * f;
}
const double E = 1e-7;
const int N = 50001;
int n, L, W, a[N], b[N];
double c, d[N];
inline bool in(double x, double y, int i) {
    return (x - a[i]) * (x - a[i]) + (y - b[i]) * (y - b[i]) <= c;
}
inline bool ck(double x, double y, double l, double w) {
    if (l < E && w < E)
        return false;
    for (R i = 1; i <= n; ++i)
        if (in(x, y, i) && in(x + l, y, i) && in(x, y + w, i) && in(x + l, y + w, i))
            return true;
    register double L = l / 2, W = w / 2;
    return ck(x, y, L, W) && ck(x + L, y, L, W) && ck(x, y + W, L, W) && ck(x + L, y + W, L, W);
}

signed main() {
    L = g(), W = g(), n = g();
    for (R i = 1; i <= n; ++i) a[i] = g(), b[i] = g();
    register double l = 0, r = 20000, md;
    while (r - l > 1e-6) {
        md = (l + r) / 2; c = md * md;
        if (ck(0, 0, L, W)) r = md;
        else l = md;
    }
    printf("%.6f\n", l);
    return 0;
}