제출 #872068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872068		Onur_Ilgaz	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	106 ms	600 KiB

odasiljaci

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
int n;
vector <pair<int, int> > points;
vector <int> par;

int parent(int x) {
	if(par[x] == x) return x;
	return par[x] = parent(par[x]);
}

void merge(int x, int y) {
	x = parent(x);
	y = parent(y);
	par[x] = y;
}

double dist(int a, int b, int x, int y) {
	return sqrt(abs(a - x) * abs(a - x) + abs(b - y) * abs(b - y));
}

bool check(double r) {
	par.assign(n, 0);
	for(int i = 0; i < n; i++) par[i] = i;
	for(int i = 0; i < n; i++) {
		int a = points[i].first, b = points[i].second;
		for(int j = 0; j < i; j++) {
			int x = points[j].first, y = points[j].second;
			// cout << a << " " << b << " " << x << " " << y << " ";
			// cout << dist(a, b, x, y) << "\n";
			if(dist(a, b, x, y) <= r * 2) {
				// cout << i << " " << j << "\n";
				merge(i, j);
			}
		}	
	}
	for(int i = 1; i < n; i++) {
		if(parent(i) != parent(0)) return 0;
	}
	return 1;
}

int32_t main(){
	fast
	cin >> n;
	for(int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		points.push_back({a, b});
	}
	double l = 0, r = 1e10;
	while(r - l > 0.0000001) {
		double m = (r + l) / 2;
		// cout << setprecision(6) << l << " " << r << " " << m << " m\n";
		if(check(m)) {
			// cout << 1 << "\n";
			r = m;
		}
		else {
			// cout << 0 << "\n";
			l = m;
		}
		// cout << "\n\n";
	}
	cout << setprecision(8) << r;
}

• Subtask 1: 70 / 70