Submission #674540

#	Time	Username	Problem	Language	Result	Execution time	Memory
674540		MacPhucKhang	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	89 ms	360 KiB

odasiljaci

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