Submission #328121

#	Time	Username	Problem	Language	Result	Execution time	Memory
328121		hhhhaura	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	648 ms	640 KiB

odasiljaci

#include <bits/stdc++.h>

#define print(x) cout << #x <<" = " << x << endl
#define pprint(x) cout << #x <<" = (" << x.first << " , " << x.second <<" )\n"
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / b)
#define all(x) x.begin(), x.end()

#define MAXN 1000005
#define INF 1000000000000000
#define MOD 1000000007
#define eps (1e-8)

#define int long long int 
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

using namespace std;
struct pt {
	lld x, y;
};
int n;
vector<pt> a;
vector<int> par, rk;
lld dis(pt a, pt b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init() {
	rep(i, 1, n) par[i] = i, rk[i] = 0;
}
int find_par(int a) {
	if(par[par[a]] == par[a]) return par[a];
	else return find_par(par[a]);
}
void unite(int a, int b) {
	int aa = find_par(a), bb = find_par(b);
	if(aa == bb) return;
	if(rk[aa] > rk[bb]) par[bb] = aa;
	else if(rk[bb] > rk[aa]) par[aa] = bb;
	else par[bb] = aa, rk[aa] ++;
	return;
}
bool check(lld x) {
	init();
	rep(i, 1, n) rep(j, i + 1, n) {
		if(dis(a[i], a[j]) <= 2 * x) unite(i, j);
	}
	int aa = find_par(1);
	rep(i, 1, n) if(find_par(i) != aa) return false;
	return true;
} 
lld solve() {
	lld l = 0, r = INF;
	while(r - l > eps) {
		lld mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	return r;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n, a.resize(n + 1);
	par.resize(n + 1), rk.resize(n + 1);
	rep(i, 1, n) cin >> a[i].x >> a[i].y;
	cout << fixed << setprecision(7) << solve() <<"\n"; 
	return 0;
} 

• Subtask 1: 70 / 70