제출 #1152607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152607		justin271828	Odašiljači (COCI20_odasiljaci)	C++17	35 / 70	425 ms	456 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;

#define double long double

const double epsilon = 1.000'000'000'000'1;

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

int main() {
	int n;
	cin >> n;
	double x[n];
	double y[n];
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	double ans = 1234567890.0;
	double lo = 0;
	double hi = ans;
	double mid;
	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*epsilon) < 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/epsilon;
		else if (!more) lo = mid*epsilon;
		else break;}
	cout << mid/2;
	return 0;}

• Subtask 1: 35 / 70