oj.uz

Submission #374360

# Submission time Handle Problem Language Result Execution time Memory
374360 2021-03-07T08:14:39 Z Araragi Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 158 ms 492 KB 
/*
* 	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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 21 ms 364 KB Output is correct
7 Correct 31 ms 364 KB Output is correct
8 Correct 69 ms 364 KB Output is correct
9 Correct 141 ms 492 KB Output is correct
10 Correct 158 ms 364 KB Output is correct