oj.uz

Submission #374351

# Submission time Handle Problem Language Result Execution time Memory
374351 2021-03-07T08:08:18 Z Araragi Odašiljači (COCI20_odasiljaci) C++17
49 / 70
 1000 ms 428 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;
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.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 4 ms 364 KB Output is correct
4 Correct 9 ms 364 KB Output is correct
5 Correct 21 ms 364 KB Output is correct
6 Correct 443 ms 428 KB Output is correct
7 Correct 576 ms 428 KB Output is correct
8 Execution timed out 1093 ms 364 KB Time limit exceeded
9 Execution timed out 1090 ms 364 KB Time limit exceeded
10 Execution timed out 1090 ms 364 KB Time limit exceeded