Submission #369584

#	Time	Username	Problem	Language	Result	Execution time	Memory
369584		penguinhacker	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	206 ms	8300 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, x[1000], y[1000];
ll d[1000][1000];
bool vis[1000];

void dfs(int i, double c) {
	vis[i] = 1;
	for (int j = 0; j < n; ++j) if (!vis[j] && d[i][j] <= 4 * c * c) dfs(j, c);
}

bool ok(double c) {
	memset(vis, 0, sizeof(vis));
	dfs(0, c);
	return count(vis, vis + n, 1) == n;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
	for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j)
		d[i][j] = d[j][i] = (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]);
	double l = 0, r = 1e9;
	for (int rep = 0; rep < 60; ++rep) {
		double mid = (l + r) / 2;
		if (ok(mid)) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(6) << l;
	return 0;
}

• Subtask 1: 70 / 70