제출 #1152263

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

odasiljaci

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define DEBUG
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	pair<int,int> a[n];
	for(int i=0;i<n;++i) {
		cin>>a[i].first>>a[i].second;
	}
	vector<pair<int,int>> adj[n]; // adj[u] = (c^2, v)
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(i!=j){
				int x=a[i].first-a[j].first, y=a[i].second-a[j].second;
				adj[i].emplace_back(x*x+y*y,j);
			}
		}
	}
	#ifdef DEBUG
	for(int i=0;i<n;++i){
		for(auto&p:adj[i]){
			cout<<"("<<p.first<<","<<p.second<<") ";
		}
		cout<<'\n';
	}
	#endif
	priority_queue<pair<int,int>> pq;
	bool vis[n]; memset(vis, 0, sizeof vis);
	vis[0]=1;
	for(auto&p:adj[0]){
		pq.emplace(-p.first,p.second);
	}
	int ans=0;
	while(pq.size()){
		pair<int,int> cur = pq.top(); pq.pop();
		if(vis[cur.second]) continue;
		
		ans=max(ans,-cur.first);
		vis[cur.second] = 1;
		for(auto&p:adj[cur.second]) {
			if(vis[p.second]) continue;
			pq.emplace(-p.first,p.second);
		}
	}
	#ifdef DEBUG
	cout<<ans<<'\n';
	#endif
	cout<<fixed<<setprecision(8)<<sqrt(ans)/2<<'\n';
	return 0;
}

• Subtask 1: 70 / 70