Submission #1208715

#TimeUsernameProblemLanguageResultExecution timeMemory
1208715catsarecool5530Mobile (BOI12_mobile)C++20
4 / 100
1097 ms47328 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define endl "\n"; #define all(x) x.begin(), x.end() #define int long long int MOD = 1e9 + 7; const ll INF = 1e18; void solve() { int n, l; cin >> n >> l; vector<array<int, 2>> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i][0] >> arr[i][1]; } auto works = [&](long double r) { vector<array<long double, 2>> cover(n); for (int i = 0; i < n; i++) { if (arr[i][1] > r) { cover[i][0] = -1e18; cover[i][1] = -1e18; continue; } cover[i][0] = arr[i][0] - sqrt(r * r - arr[i][1] * arr[i][1]); cover[i][1] = arr[i][0] + sqrt(r * r - arr[i][1] * arr[i][1]); } sort(all(cover)); long double cur = 0; for (int i = 0; i < n; i++) { if (cover[i][0] > cur) continue; cur = max(cur, cover[i][1]); } return cur >= l; }; long double l1 = 0, r = 1e9; while (r - l1 > 1e-9) { long double mid = (l1 + r) / 2; if (works(mid)) { r = mid; } else { l1 = mid; } } cout << fixed << setprecision(10) << r << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(NULL); // freopen("walk.in", "r", stdin); // freopen("walk.out", "w", stdout); ll t = 1; // cin >> t; while (t--) { solve(); } }
#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...