Submission #807324

#	Time	Username	Problem	Language	Result	Execution time	Memory
807324		Tunglam07	Odašiljači (COCI20_odasiljaci)	C++17	42 / 70	987 ms	320 KiB

odasiljaci

#include<bits/stdc++.h>
using namespace std;

long long n, parent[1001], limit = 100;
double lt = 0, rt = 1e9;

pair<int, int> a[1001];
 
int findparent(int id)
{
	if(id == parent[id])
	{
		return id;
	}
	else	
	{
		return parent[id] = findparent(parent[id]);
	}
}
 
bool check(double id)
{
	for(int i = 1; i <= n; ++i)	
	{
		parent[i] = i;
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
		{
			double temp = (a[i].first - a[j].first) * (a[i].first - a[j].first) + (a[i].second - a[j].second) * (a[i].second - a[j].second);
			if(sqrt(temp) < id * 2)
			{
				long long a = findparent(i), b = findparent(j);
				parent[a] = parent[b];
			}
		}
	}
	parent[1] = findparent(1);
	for(int i = 2; i <= n; ++i)	
	{
		if(findparent(i) != parent[1])	
		{
			return 0;
		}	
	}
	return 1;
}
 
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)	
	{
		cin >> a[i].first >> a[i].second;
	}
	while(lt < rt && limit--)
	{
		double mid = (lt + rt) / 2;
		if(!check(mid))	
		{
			lt = mid;
		}
		else	
		{
			rt = mid;
		}
	}
	cout << setprecision(7) << fixed << lt;
}

• Subtask 1: 42 / 70