제출 #374351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374351		Araragi	Odašiljači (COCI20_odasiljaci)	C++17	49 / 70	1093 ms	428 KiB

odasiljaci

/*
* 	author: Araragi
*/

// 3

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

#define pb push_back
#define F first
#define S second
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const double EPS = 1e-7;

vector<double> x, y;
map<int, bool> vis;
int n;
int visitedPoints;

ll get_dist(double xs, double ys, double xf, double yf)
{
	return (ll)((xs - xf) * (xs - xf) + (ys - yf) * (ys - yf));
}

void rec(int v, double r)
{
	vis[v] = 1;

	for (int i = 0; i < n; i++)
		if (!vis[i] && get_dist(x[v], y[v], x[i], y[i]) <= (ll)4 * r * r)
			rec(i, r);
}

bool ok(double r)
{
 	vis.clear();
              
    rec(0, r);

    int visited = 0;
    for (int i = 0; i < n; i++)
    	if (vis[i])
    		visited++;

    return (visited == n);
}


int main()
{
	//ifstream cin("vacation.in");
	//ofstream cout("vacation.out");
	
	cin >> n;

	x.resize(n);
	y.resize(n);

	for (int i = 0; i < n; i++)
		cin >> x[i] >> y[i];

	double l = 0, r = 1e9;
	double ans = 1e9;
	while (r - l > EPS)
	{       
		double md = (l + r) / 2;

		if (ok(md))
			ans = min(ans, md);

		if (ok(md))
			r = md;
		else
			l = md;
	}

	cout << setprecision(7) << fixed << ans;
}

• Subtask 1: 49 / 70