Untitled
unknown
c_cpp
a year ago
2.1 kB
8
Indexable
#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct DSU {
vector<T> sz, parent;
int n;
DSU(int n) : n(n) {
sz = parent = vector<T>(n, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x, y);
parent[y] = x;
sz[x] += sz[y];
}
};
int x, y;
struct pt {
long double x, y;
pt(long double x = 0, long double y = 0) : x(x), y(y) {};
};
bool overlap(pt p1, pt p2, long double r) {
long double dist = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
return dist < 4 * r * r;
}
bool in(pt p1, pt p2, long double r) {
long double dist = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
return dist < r * r;
}
bool touchWN(pt p1, long double r) {
return in(p1, pt(0, p1.y), r) || in(p1, pt(p1.x, y), r);
}
bool touchES(pt p1, long double r) {
return in(p1, pt(p1.x, 0), r) || in(p1, pt(x, p1.y), r);
}
int n;
vector<pt> v;
bool can(long double r) {
DSU<int> dsu(n + 3);
for (int i = 0; i < n; ++i) {
if (touchES(v[i], r))
dsu.uni(i, n);
if (touchWN(v[i], r))
dsu.uni(i, n + 1);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (overlap(v[i], v[j], r)) {
dsu.uni(i, j);
}
}
}
return dsu.find(n) != dsu.find(n + 1);
}
int main() {
cin >> x >> y >> n;
v.resize(n);
for (int i = 0; i < n; ++i) {
long double a, b;
cin >> a >> b;
v[i] = {a, b};
}
long double l = 0, r = 1e9, ans;
while (r - l >= 1e-10) {
long double mid = (l + r) / 2;
if (can(mid)) {
ans = mid;
l = mid;
} else {
r = mid;
}
}
cout << fixed << setprecision(5) << ans;
}Editor is loading...
Leave a Comment