Submission #1321204

#TimeUsernameProblemLanguageResultExecution timeMemory
1321204murad_mirzebeyliOdašiljači (COCI20_odasiljaci)C++20
21 / 70
255 ms9064 KiB
#include <bits/stdc++.h> #define endl '\n' #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define F first #define S second #define pf push_front #define pb push_back #define ll long long #define ull unsigned long long #define ld long double #define int long long #define vi vector <int> #define pii pair <int,int> #define tiii tuple<int,int,int> #define yes cout << "Yes" << endl #define no cout << "No" << endl #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define out(v) for (auto x:v) cout << x << ' ' #define out1(v) for (auto x:v) cout << x << endl #define inp(arr) for (int i=0;i<arr.size();i++) cin>>arr[i] const int MAX=1e6; const int MOD=1e9+7; using namespace std; const int inf=1e18; void solve(){ int n; cin>>n; vector<pii> vt(n+1); for(int i=1;i<=n;i++){ cin>>vt[i].F>>vt[i].S; } if(n==1){ cout<<0<<endl; return; } double l=0.0,r=1e13,best=0.0; for(int k=0;k<100;k++){ int m=(l+r)/2.0; vi arr[n+5]; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ double a=vt[i].F-vt[j].F; double b=vt[i].S-vt[j].S; if(sqrt(a*a+b*b)<=2*m){ arr[i].pb(j); arr[j].pb(i); } } } vi dis(n+5,-1); queue<int> q; q.push(1); dis[1]=0; while(q.size()){ int u=q.front(); q.pop(); for(int i:arr[u]){ if(dis[i]==-1) { q.push(i); dis[i]=dis[u]+1; } } } bool ok=true; for(int i=1;i<=n;i++){ if(dis[i]==-1) ok=false; } if(ok){ best=m; r=m; } else l=m; } cout<<setprecision(7)<<fixed<<best<<endl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...