90 pts 玄关
查看原帖
90 pts 玄关
1046223
a_blue_fool楼主2024/11/19 21:40
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>

#define N (3000 + 5)
#define K -1e6

using namespace std;

int n, row, line, cnt1, cnt2;
double l, r, mid, ans;
double x[N], y[N];
double dis[N][N];
bool vis[N];

double dist(double x1, double y1, double x2, double y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

bool check(double dis,  double k) {
	return 4 * k * k > dis;
}

bool cmp (double r) {
	memset(vis, 0, sizeof(vis));
	queue <int> q;
	
	for (int i = 1; i <= n; i++)
		if (x[i] < r || row - y[i] < r) {
			q.push(i);
			vis[i] = true;
		}
	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		
		if (line - x[u] < r || y[u] < r)
			return false;
		
		for (int i = 1; i <= n; i++)
			if (!vis[i] && check(dis[u][i], r)) {
				vis[i] = true;
				q.push(i);
			}
	}
	
	return true;
}

int main() {
	scanf("%d%d%d", &n, &row, &line);
	row--, line--;
	
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
		x[i]--, y[i]--;
	}
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			dis[i][j] = dis[j][i] = dist(x[i], y[i], x[j], y[j]);
	
	r = min(row, line);
	for (int i = 1; i <= 60; i++) {
		mid = (l + r) / 2;
		
		if (cmp(mid))
			l = mid;
		else 
			r = mid;
	}
	
	printf("%.2lf", l);
	return 0;
}
2024/11/19 21:40
加载中...