Submission #334685

#	Time	Username	Problem	Language	Result	Execution time	Memory
334685		nikatamliani	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	375 ms	492 KiB

odasiljaci

#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 / 70