Submission #1240727

#TimeUsernameProblemLanguageResultExecution timeMemory
1240727ZeroMobile (BOI12_mobile)C++20
0 / 100
1099 ms196608 KiB
#include <bits/stdc++.h> #define f first #define ss second using namespace std; bool ok(double r, const vector<pair<int, int>>& a, int x_target) { int n = a.size(); vector<vector<int>> g(n); // Build graph for(int i = 0; i < n; ++i){ for(int j = i+1; j < n; ++j){ double dx = a[i].f - a[j].f; double dy = a[i].ss - a[j].ss; if(dx*dx + dy*dy <= 4*r*r){ g[i].push_back(j); g[j].push_back(i); } } } // Find which phones can reach x=0 and which can reach x=x_target vector<int> starts, targets; for(int i = 0; i < n; ++i){ if(a[i].f - r <= 0) starts.push_back(i); if(a[i].f + r >= x_target) targets.push_back(i); } // Try to reach from any start to any target queue<int> q; vector<bool> visited(n, false); for(int s : starts){ q.push(s); visited[s] = true; } while(!q.empty()){ int u = q.front(); q.pop(); for(int v : g[u]){ if(!visited[v]){ visited[v] = true; q.push(v); } } } for(int t : targets){ if(visited[t]) return true; } return false; } signed main(){ cin.tie(0)->sync_with_stdio(0); int n,x; cin >> n >> x; vector<pair<int,int>> a(n); for(auto &i : a) cin >> i.first >> i.second; double l = 0, r = INT_MAX; for(int i=0; i < 100; i ++){ double m = (l + r) / 2; if(ok(m,a,x)) r = m; else l=m; } cout << fixed << setprecision(6) << r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...