oj.uz

Submission #522918

# Submission time Handle Problem Language Result Execution time Memory
522918 2022-02-06T12:51:17 Z tato Odašiljači (COCI20_odasiljaci) C++14
42 / 70
 59 ms 8168 KB 
#include <bits/stdc++.h>

#define ll long long



using namespace std;

double eps = 0.000001;
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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 588 KB Output isn't correct
5 Incorrect 2 ms 716 KB Output isn't correct
6 Correct 9 ms 4172 KB Output is correct
7 Correct 14 ms 4236 KB Output is correct
8 Correct 30 ms 6224 KB Output is correct
9 Incorrect 59 ms 8168 KB Output isn't correct
10 Incorrect 56 ms 8140 KB Output isn't correct