oj.uz

답안 #522926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522926 2022-02-06T13:04:17 Z tato Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 152 ms 16012 KB 
#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.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 15 ms 6240 KB Output is correct
7 Correct 26 ms 6244 KB Output is correct
8 Correct 61 ms 12108 KB Output is correct
9 Correct 128 ms 16012 KB Output is correct
10 Correct 152 ms 15948 KB Output is correct