Submission #1320466

#TimeUsernameProblemLanguageResultExecution timeMemory
1320466zainabsattarliOdašiljači (COCI20_odasiljaci)C++20
70 / 70
270 ms9432 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n;cin>>n;vector<pair<int, int>>vt; for(int i=1;i<=n;i++){int a,b;cin>>a>>b;vt.push_back({a, b});} double l=0.0,r=1e15, best=0.0; for(int times=1;times<=100;times++){ double m=1.0* (l+r)/2;vector<int>adj[n+5]; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ pair<int, int>p1=vt[i-1],p2=vt[j-1]; if(sqrt(abs(p1.first-p2.first)*abs(p1.first-p2.first)+abs(p1.second-p2.second) *abs(p1.second-p2.second))/2<=m){adj[i].push_back(j);adj[j].push_back(i);}}} int dis[n+5]; memset(dis,-1,sizeof(dis)); queue<int>q;q.push(1);dis[1]=0; while(q.size()){int x=q.front();q.pop(); for(int i : adj[x]){ if(dis[i]==-1){q.push(i);dis[i]=dis[x]+1;}}} bool ok=true; for(int i=1;i<=n;i++)if(dis[i]==-1)ok=false; if(ok){r=m;best=m;} else l = m; } cout<<setprecision(7)<<fixed<<best<<"\n"; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...