oj.uz

답안 #872068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872068 2023-11-12T08:49:48 Z Onur_Ilgaz Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 106 ms 600 KB 
#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.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 30 ms 456 KB Output is correct
7 Correct 30 ms 348 KB Output is correct
8 Correct 69 ms 484 KB Output is correct
9 Correct 106 ms 348 KB Output is correct
10 Correct 96 ms 600 KB Output is correct