Submission #904035

#	Time	Username	Problem	Language	Result	Execution time	Memory
904035		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	136 ms	684 KiB

odasiljaci

# include <bits/stdc++.h>

using namespace std;

const double eps = 1e-8;

const int N = 1e3+5;

int n, components, f[N], de[N];
double x[N], y[N];
int find(int u) {return f[u]==u? u: f[u] = find(f[u]);}
void unite(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu==fv) return ;
	if (de[fu] < de[fv]) swap(fu, fv);
	--components;
	f[fv] = fu;
	de[fu] = max(de[fu], de[fv]+1);
}

bool close(int u, int v, double R) {
	return (x[u]-x[v])*(x[u]-x[v]) + (y[u]-y[v])*(y[u]-y[v]) <= 4.0*R*R; 
}

bool check(double R) {
	components = n;
	iota(f+1, f+1+n, 1);
	fill(de+1, de+1+n, 0);
	for (int i=1; i<=n; ++i) {
		for (int j=1; j<=n; ++j) {
			if (close(i, j, R)) unite(i, j);
		}
	}	
	return components == 1;
}

int main() {
	cin >> n;
	for (int i=1; i<=n; ++i) cin >> x[i] >> y[i];
	double l = 0, r = 1e9+7;
	while (l + eps < r) {
		double mid = (l+r)/2.0;
		if (check(mid)) r = mid;
		else l = mid;
	}
	cout << setprecision(8) << r << '\n';
	return 0;
}

• Subtask 1: 70 / 70