eolymp
bolt
Try our new interface for solving problems
Problems

Safe Distance

published at 3/22/24, 3:32:39 pm

include <iostream>

include <cmath>

include <algorithm>

using namespace std;

const int MAX_N = 1005; const double EPS = 1e-8;

struct Point { double x, y; double Distance(Point& other) { return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y)); } } people[MAX_N + 5];

struct CircleSets { double minx[MAXN], maxx[MAXN], miny[MAXN], maxy[MAXN]; int p[MAX_N], rank[MAX_N]; int n; // Добавленная переменная n

void Init(int n, double radius) { // Измененный метод Init
    this->n = n;
    for (int i = 0; i < n; ++i) {
        min_x[i] = people[i].x - radius;
        max_x[i] = people[i].x + radius;
        min_y[i] = people[i].y - radius;
        max_y[i] = people[i].y + radius;
        p[i] = i;
        rank[i] = 0;
    }
}

int Repr(int n) {
    if (n == p[n]) return n;
    return p[n] = Repr(p[n]);
}

void Join(int i, int j) {
    i = Repr(i);
    j = Repr(j);
    if (i == j) return;
    if (rank[i] > rank[j]) swap(i, j);
    p[i] = j;
    if (rank[i] == rank[j]) rank[j]++;
    min_x[j] = min(min_x[j], min_x[i]);
    max_x[j] = max(max_x[j], max_x[i]);
    min_y[j] = min(min_y[j], min_y[i]);
    max_y[j] = max(max_y[j], max_y[i]);
}

bool HasPath(double x, double y) { // Измененный метод HasPath
    for (int i = 0; i < n; i++) {
        if (p[i] != i) continue;
        if (min_x[i] < 0 && max_x[i] > x) return false;
        if (min_y[i] < 0 && max_y[i] > y) return false;
        if (min_x[i] < 0 && min_y[i] < 0) return false;
        if (max_x[i] > x && max_y[i] > y) return false;
    }
    return true;
}

};

int n; double x, y;

bool IsSafe(double radius) { CircleSets circle_sets; circle_sets.Init(n, radius); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (people[i].Distance(people[j]) < 2 * radius) circle_sets.Join(i, j); return circle_sets.HasPath(x, y); }

double MaxSafeDistance() { double left = 0, right = min(x, y); while (right - left > EPS) { double mid = left + (right - left) / 2; if (IsSafe(mid)) left = mid; else right = mid; } return left; }

int main() { cin >> x >> y >> n; for (int i = 0; i < n; ++i) cin >> people[i].x >> people[i].y;

cout << MaxSafeDistance() << endl;

return 0;

}