Submission #1152264

#TimeUsernameProblemLanguageResultExecution timeMemory
1152264gelastropodOdašiljači (COCI20_odasiljaci)C++20
35 / 70
274 ms16796 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> tree;

int fin(int n) {
	if (tree[n] == n) return n;
	return tree[n] = fin(tree[n]);
}

void join(int a, int b) {
	a = fin(a);
	b = fin(b);
	if (a == b) return;
	tree[b] = a;
}

signed main() {
	int n, x, y;
	cin >> n;
	vector<pair<int, int>> coords;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		coords.push_back({ x, y });
	}
	priority_queue<pair<long double, pair<int, int>>, vector<pair<long double, pair<int, int>>>, greater<pair<long double, pair<int, int>>>> pq;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			pq.push({ pow((coords[i].first - coords[j].first) * (coords[i].first - coords[j].first) + (coords[i].second - coords[j].second) * (coords[i].second - coords[j].second), (long double)0.5), {i, j} });
	for (int i = 0; i < n; i++)
		tree.push_back(i);
	long double ans = -1;
	while (!pq.empty()) {
		if (fin(pq.top().second.first) != fin(pq.top().second.second)) {
			ans = max(ans, pq.top().first);
			join(pq.top().second.first, pq.top().second.second);
		}
		pq.pop();
	}
	cout << ans / 2 << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...