제출 #1152262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152262		thelegendary08	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	406 ms	17348 KiB

odasiljaci

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<long long int>
#define ll long long int 
#define mp make_pair
#define pii pair<ll,ll>
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
ll dist(pii a, pii b){
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int main(){
	int n;
	cin>>n;
	vector<pair<ll,ll>>pts;
	f0r(i,n){
		ll a,b;
		cin>>a>>b;
		pts.pb(mp(a,b));
	}
	ll lo = 0;
	ll hi = 4e18;
	while(lo < hi){
		ll mid = (lo + hi) / 2;
		vector<vi>adj(n);
		f0r(i,n){
			f0r(j,n){
				if(i != j){
					if(dist(pts[i], pts[j]) <= mid){
						adj[i].pb(j);
						adj[j].pb(i);
					}
				}
			}
		}
		vector<bool>vis(n);
		queue<int>q;
		q.push(0);
		vis[0] = 1;
		while(!q.empty()){
			int node = q.front();
			q.pop();
			for(auto u : adj[node]){
				if(vis[u])continue;
				vis[u] = 1;
				q.push(u);
			}
		}
		bool ok = 1;
		f0r(i,n)if(!vis[i])ok = 0;
		if(ok){
			hi = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	cout<<fixed;
	cout<<setprecision(17);
	cout<<sqrt(lo)/2.0<<'\n';
}

• Subtask 1: 70 / 70