Submission #489670

#	Time	Username	Problem	Language	Result	Execution time	Memory
489670		fuad27	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	103 ms	392 KiB

odasiljaci

#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 / 70