oj.uz

Submission #369584

# Submission time Handle Problem Language Result Execution time Memory
369584 2021-02-22T00:34:04 Z penguinhacker Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 206 ms 8300 KB 
#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.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 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 28 ms 4332 KB Output is correct
7 Correct 29 ms 4332 KB Output is correct
8 Correct 80 ms 6252 KB Output is correct
9 Correct 161 ms 8172 KB Output is correct
10 Correct 206 ms 8300 KB Output is correct