제출 #1152652

#제출 시각아이디문제언어결과실행 시간메모리
1152652justin271828Odašiljači (COCI20_odasiljaci)C++20
63 / 70
306 ms456 KiB
#include <bits/stdc++.h>
using namespace std;

long double sq(long double x) {return x*x;}

int main() {
	int n;
	cin >> n;
	long double x[n];
	long double y[n];
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	long double ans = 1234567890.0;
	long double lo = 0;
	long double hi = ans;
	long double mid = 0.12302399238832;
	bool v[n];
	while (true) {
		mid = (lo+hi)/2;
		queue<int> q;
		q.push(0);
		memset(v, false, sizeof(v));
		v[0] = true;
		while (!q.empty()) {
			int temp = q.front();
			for (int i = 0; i < n; i++) {
				if (i == temp) continue;
				if (sq(mid) < sq(x[temp]-x[i])+sq(y[temp]-y[i])) continue;
				if (v[i]) continue;
				v[i] = true;
				q.push(i);}
			q.pop();}
		bool less = true;
		for (bool b: v) less = (less && b);
		q.push(0);
		memset(v, false, sizeof(v));
		v[0] = true;
		while (!q.empty()) {
			int temp = q.front();
			for (int i = 0; i < n; i++) {
				if (i == temp) continue;
				if (sq(mid*1.00000001) < sq(x[temp]-x[i])+sq(y[temp]-y[i])) continue;
				if (v[i]) continue;
				v[i] = true;
				q.push(i);}
			q.pop();}
		bool more = true;
		for (bool b: v) more = (more && b);
		if (less) hi = mid;
		else if (!more) lo = mid;
		else break;}
	mid /= 2;
	long double ten = 10000000000.0;
	int count = 0;
	for (int i = 0; i < 19; i++) {
	    if (i == 11) cout << ".";
	    while (mid >= ten) {
	        count++;
	        mid -= ten;
	    }
	    if (count > 0 || i >= 10) cout << count;
	    ten /= 10;
	    count = 0;
	}
	return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...