oj.uz

Submission #489670

# Submission time Handle Problem Language Result Execution time Memory
489670 2021-11-23T18:19:10 Z fuad27 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 103 ms 392 KB 
#include<bits/stdc++.h>
using namespace std;
const long double eps = 1e-7;
int n, cnt;
const int maxn = 1010;
pair<int, int> v[maxn];
bool visited[maxn];
long double dist(pair<int, int> x, pair<int, int> y) {
	return sqrt((long double)(x.first - y.first) * (x.first - y.first) +
	       (long double)(x.second - y.second) * (x.second - y.second));
}
void dfs(int x, long double r) {
	cnt++;
	visited[x] = 1;
	for (int i = 0; i < n; i++) {
		if (i != x and visited[i] == 0 and dist(v[x], v[i]) < 2 * r) {
			dfs(i, r);
		}
	}
}
bool check(long double r) {
	memset(visited, 0, sizeof visited);
	cnt = 0;	
	dfs(0, r);
	return cnt == n;
}
int main () {
	cin >> n;
	for(int i = 0;i<n;i++) {
		cin >> v[i].first >> v[i].second;
	}
	long double l = 0, r=1e9, m, ans = 0;
	while(l < r) {
		m = (l+r)/2.0;
		if(check(m)) {
			r = m-eps;
			ans = m;
		}
		else {
			l = m + eps;
		}
	}
	cout << fixed << setprecision(7) << ans << endl;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Correct 15 ms 348 KB Output is correct
7 Correct 19 ms 348 KB Output is correct
8 Correct 47 ms 336 KB Output is correct
9 Correct 102 ms 336 KB Output is correct
10 Correct 103 ms 392 KB Output is correct