oj.uz

Submission #334685

# Submission time Handle Problem Language Result Execution time Memory
334685 2020-12-09T18:58:58 Z nikatamliani Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 375 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define ll long long
int p[N], s[N], n;
long double x[N], y[N]; 
int find_set(int x) {
	return x == p[x] ? x : find_set(p[x]);
}
bool union_sets(int x, int y) {
	x = find_set(x);
	y = find_set(y);
	if(x == y) {
		return false;
	}
	if(s[x] > s[y]) {
		swap(x, y); 
	}
	s[y] += s[y];
	p[x] = y;
	return true;
}
bool check(long double r) {
	auto square = [&](long double x) {
		return x * x;
	};
	for(int i = 1; i <= n; ++i) {
		p[i] = i;
		s[i] = 1;
	}
	int components = n;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < i; ++j) {
			if(square(x[i] - x[j]) + square(y[i] - y[j]) <= square(2 * r)) {
				components -= union_sets(i, j); 
			}
		}
	}
	return components == 1;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout << setprecision(13) << fixed; 
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
	}
	long double l = 0, r = 1e9, ans = -1, eps = 1e-9;
	for(int it = 0; it < 100; ++it) {
		long double m = (l + r) * 0.5;
		if(check(m)) {
			ans = m;
			r = m - eps;
		} else {
			l = m + eps;
		}
	}
	cout << ans << '\n';
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Correct 98 ms 472 KB Output is correct
7 Correct 98 ms 364 KB Output is correct
8 Correct 241 ms 492 KB Output is correct
9 Correct 375 ms 364 KB Output is correct
10 Correct 292 ms 492 KB Output is correct