제출 #1236097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236097		PlayVoltz	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	132 ms	25236 KiB

odasiljaci

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

#define int long double
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> dsu;

int fp(int a){
	if (dsu[a]==-1)return a;
	return dsu[a]=fp(dsu[a]);
}

bool merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a==b)return 0;
	dsu[a]=b;
	return 1;
}

int calc(pii a, pii b){
	return sqrt((a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, ans=0;
	cin>>n;
	vector<pii> vect(n);
	vector<pair<int, pii> > edges;
	dsu.resize(n, -1);
	for (int i=0; i<n; ++i)cin>>vect[i].fi>>vect[i].se;
	for (int i=0; i<n; ++i)for (int j=i+1; j<n; ++j)edges.pb(mp(calc(vect[i], vect[j]), mp(i, j)));
	sort(edges.begin(), edges.end());
	for (auto c:edges)if (merge(c.se.fi, c.se.se))ans=c.fi;
	cout<<fixed<<setprecision(9)<<ans/2.0;
}

• Subtask 1: 70 / 70