Submission #522917

#	Time	Username	Problem	Language	Result	Execution time	Memory
522917		tato	Odašiljači (COCI20_odasiljaci)	C++14	42 / 70	76 ms	8188 KiB

odasiljaci

#include <bits/stdc++.h>

#define ll long long



using namespace std;

double eps = 0.0000001;
double g[1001][1001];
int used[1001];
int n, cnt ;

double length(int x1,int y1,int x2, int y2)
{
	
	
	double s = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
	return s;
}
void dfs(int v,double mid)
{
	used[v] = 1;
	
	for(int i = 1; i <= n; i++)
			if(mid >= g[v][i] and used[i] == 0)
				dfs(i,mid);
				
	cnt++;	
				
	
	
}
bool check(double mid)
{
	for(int i = 1; i <= n; i++)
		{
			used[i] = 0;
			
		}
	
	cnt = 0;
	
	dfs(1,mid);
	
	if(cnt == n)
		return true;
	else
		return false;
		
}
void answer()
{
	int x, y;
	vector <pair <int,int > > v;
	v.push_back({0,0});
	
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		{
			cin >> x >> y;
			
			v.push_back({x, y});
		}
	double mx = eps;
	for(int i = 1; i < n; i++)
		for(int j = i + 1; j <= n; j++)
			{
				g[i][j] = length(v[i].first, v[i].second, v[j].first, v[j].second);
				g[j][i] = g[i][j];
				
				mx = max(mx, g[i][j]);
			}
	
	double l = eps, r = mx;
	
	while((r - l) > eps)
		{
			double mid = (l + r) / 2;
			
			
			if(check(mid))
				r = mid;
			else
				l = mid + eps;
				
		} 
		r /= 2;
		cout << fixed << setprecision(7) << r;
	
}

int main()
{
	int t = 1;
	// cin >> t;
	
	while(t--)
		answer();
		
	return 0;
	
	
	
}

• Subtask 1: 42 / 70