Submission #1093753

#TimeUsernameProblemLanguageResultExecution timeMemory
1093753michifiedMobile (BOI12_mobile)C++17
100 / 100
867 ms35156 KiB
#include <bits/stdc++.h> #define ll long long #define ld double #define lid id * 2 + 1 #define rid id * 2 + 2 using namespace std; const ll mod = 1e9 + 7; struct coord_t { ll x, y; }; bool all(ld rad, ld l, vector<coord_t>& towers) { ld cur = 0, radsq = rad * rad; for (auto& t : towers) { if (t.y > rad) continue; ld horiz = sqrt(radsq - (t.y * t.y)); if (t.x - horiz > cur) continue; cur = max(cur, t.x + horiz); } return cur >= l; } int main() { // ifstream cin("valleys.in"); // ofstream cout("valleys.out"); ld n, L, i; ll tx, ty; cin >> n >> L; vector<coord_t> towers(n); for (i = 0; i < n; i++) { cin >> tx >> ty; towers[i] = {tx, ty}; } ld l = 1, r = 1.5e9, tol = 0.001; while (l < r - tol) { ld mid = (l + r) / 2; if (not all(mid, L, towers)) l = mid; else r = mid; } cout << fixed << setprecision(4) << l; return 0; }
#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...