oj.uz

Submission #674540

# Submission time Handle Problem Language Result Execution time Memory
674540 2022-12-25T04:23:24 Z MacPhucKhang Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 89 ms 360 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1005;
const double eps = 1e-7;

int n, vis;
pii o[maxn];
bool bio[maxn];

ll dist_sqrd(pii x, pii y) {
	return (ll)(x.first - y.first) * (x.first - y.first) +
	       (ll)(x.second - y.second) * (x.second - y.second);
}

void dfs(int x, double r) {
	vis++;
	bio[x] = 1;
	for (int i = 0; i < n; i++)
		if (i != x && bio[i] == 0 && dist_sqrd(o[x], o[i]) < (ll) 4 * r * r) 
			dfs(i, r);
}

bool ok(double r) {
	memset(bio, 0, sizeof bio);
	vis = 0;	
	dfs(0, r);
	return vis == n;
}
	
int main (){	
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> o[i].first >> o[i].second;
	double lo = 0;
	double hi = 1e9;
	while (hi - lo > eps) {
		double mid = (lo + hi) / 2;
		if (ok(mid))
			hi = mid;
		else
			lo = mid;	
	}
	cout << fixed << setprecision(7) << lo;
	return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 13 ms 340 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Correct 40 ms 340 KB Output is correct
9 Correct 79 ms 360 KB Output is correct
10 Correct 89 ms 300 KB Output is correct