Submission #374360

#	Time	Username	Problem	Language	Result	Execution time	Memory
374360		Araragi	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	158 ms	492 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;
bool vis[1001];
int n;
int visited;

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;
	visited++;

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

bool ok(double r)
{
	for (int i = 0; i < n; i++)
		vis[i] = 0;

 	visited = 0;
          
    rec(0, r);


    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;
	while (r - l > EPS)
	{       
		double md = (l + r) / 2;

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

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

• Subtask 1: 70 / 70