Submission #1352069

#TimeUsernameProblemLanguageResultExecution timeMemory
1352069jumpOdašiljači (COCI20_odasiljaci)C++20
35 / 70
44 ms33256 KiB
#include <bits/stdc++.h>
#define int long long

std::priority_queue<std::pair<long double,std::pair<int,int>>> pq;
long double x[1010];
long double y[1010];
int dsu[1010];
int find(int num){
	if(dsu[num]==num)return num;
	else return dsu[num]=find(dsu[num]);
}
void unionS(int n1,int n2){
	int p1=find(n1);
	int p2=find(n2);
	dsu[p1]=p2;
}
signed main() {
	int n;
	std::cin >> n;
	for(int i=1;i<=n;i++)std::cin >> x[i] >> y[i],dsu[i]=i;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)pq.push({-std::sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])),{i,j}});
	int setsum = n;
	long double sum = 0;
	while(!pq.empty()&&setsum>1){
		long double dist = -pq.top().first;
		int n1=pq.top().second.first;
		int n2=pq.top().second.second;
		pq.pop();
		if(find(n1)!=find(n2)){
			unionS(n1,n2);
			setsum-=1;
			sum=std::max(sum,dist/2);
		}
	}
	std::cout << sum;
}
#Verdict Execution timeMemoryGrader output
Fetching results...