oj.uz

Submission #904035

# Submission time Handle Problem Language Result Execution time Memory
904035 2024-01-11T18:11:47 Z vjudge1 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 136 ms 684 KB 
# include <bits/stdc++.h>

using namespace std;

const double eps = 1e-8;

const int N = 1e3+5;

int n, components, f[N], de[N];
double x[N], y[N];
int find(int u) {return f[u]==u? u: f[u] = find(f[u]);}
void unite(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu==fv) return ;
	if (de[fu] < de[fv]) swap(fu, fv);
	--components;
	f[fv] = fu;
	de[fu] = max(de[fu], de[fv]+1);
}

bool close(int u, int v, double R) {
	return (x[u]-x[v])*(x[u]-x[v]) + (y[u]-y[v])*(y[u]-y[v]) <= 4.0*R*R; 
}

bool check(double R) {
	components = n;
	iota(f+1, f+1+n, 1);
	fill(de+1, de+1+n, 0);
	for (int i=1; i<=n; ++i) {
		for (int j=1; j<=n; ++j) {
			if (close(i, j, R)) unite(i, j);
		}
	}	
	return components == 1;
}

int main() {
	cin >> n;
	for (int i=1; i<=n; ++i) cin >> x[i] >> y[i];
	double l = 0, r = 1e9+7;
	while (l + eps < r) {
		double mid = (l+r)/2.0;
		if (check(mid)) r = mid;
		else l = mid;
	}
	cout << setprecision(8) << r << '\n';
	return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 53 ms 436 KB Output is correct
7 Correct 50 ms 432 KB Output is correct
8 Correct 136 ms 440 KB Output is correct
9 Correct 116 ms 684 KB Output is correct
10 Correct 100 ms 344 KB Output is correct