제출 #1152282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152282		gelastropod	Odašiljači (COCI20_odasiljaci)	C++20	21 / 70	838 ms	16908 KiB

odasiljaci

#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;
}

long double dist(pair<long double, long double> a, pair<long double, long double> b) {
	return pow((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second), (long double)0.5);
}

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++) {
			pair<long double, long double> midpoint = { (coords[i].first + coords[j].first) / 2, (coords[i].second + coords[j].second) / 2 };
			pair<int, int> lattice = { 0, 0 };
			long double crntmin = 1e10;
			for (int k = 0; k < 2; k++) {
				for (int l = 0; l < 2; l++) {
					if (dist(midpoint, { (int)midpoint.first + k, (int)midpoint.second + l }) < crntmin) {
						crntmin = dist(midpoint, { (int)midpoint.first + k, (int)midpoint.second + l });
						lattice = { (int)midpoint.first + k, (int)midpoint.second + l };
					}
				}
			}
			long double dist1 = dist(coords[i], lattice);
			long double dist2 = dist(coords[j], lattice);
			pq.push({ (dist1 + dist2) / 2, {i, j} });
		}
	}
	for (int i = 0; i < n; i++)
		tree.push_back(i);
	long double ans = 0;
	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 << '\n';
}

• Subtask 1: 21 / 70