제출 #522926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522926		tato	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	152 ms	16012 KiB

odasiljaci

#include <bits/stdc++.h>

#define ll long long



using namespace std;

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

long  double length(ll x1,ll y1,ll x2, ll y2)
{
	
	
    long double s = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
	return s;
}
void dfs(int v,long 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(long 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()
{
	ll x, y;
	vector <pair <ll,ll > > v;
	v.push_back({0,0});
	
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		{
			cin >> x >> y;
			
			v.push_back({x, y});
		}
	long 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]);
			}
	
	long double l = eps, r = mx;
	
	while((r - l) >= eps)
		{
			long 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: 70 / 70