rt,wa on 4,但是和答案差别不到 10−6。
int x[N], y[N];
// dist^2
int dist(int x, int y, int xx, int yy) {
return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}
int w, h, n;
int chk(int xx, int yy) {
int m1 = 4e18, m2 = 4e18;
for (int i = 1; i <= n; ++i) {
int fin = dist(xx, yy, x[i], y[i]);
if (fin < m1) m2 = m1, m1 = fin;
else if (fin < m2) m2 = fin;
}
return m2;
}
void run() {
srand(time(0));
w = read(), h = read(), n = read();
for (int i = 1; i <= n; ++i) x[i] = read(), y[i] = read();
long double x = Rand(0, w), y = Rand(0, h);
int last = chk(x, y), mx = last;
while (1. * clock() / CLOCKS_PER_SEC <= 1.75) {
for (long double tem = 1e6; tem >= 1e-12; tem *= 0.999) {
long double xx = Rand(max(0.0L, x - tem), min((long double)w, x + tem)), yy = Rand(max(0.0L, y - tem), min((long double)h, y + tem));
int now = chk(xx, yy), delta = last - now;
mx = max({mx, now, last});
if (delta < 0 || Rand(0, 1) < exp(-delta / tem)) x = xx, y = yy, last = now;
// cout << "qwq " << Rand(0, 1) << ' ' << expl(-delta / tem) << ' ' << delta << ' ' << tem << '\n'; _sleep(250);
}
}
printf("%.25Lf\n", sqrtl(mx));
}