Submission #1236811

#TimeUsernameProblemLanguageResultExecution timeMemory
1236811cjspd_olyMobile (BOI12_mobile)C++17
0 / 100
110 ms8264 KiB
#include <bits/stdc++.h> using namespace std; const double EPS = 1e-6; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; double L; cin >> N >> L; vector<pair<int, int>> stations(N); for (int i = 0; i < N; ++i) cin >> stations[i].first >> stations[i].second; auto dist = [](double x, int px, int py) -> double { double dx = x - px; double dy = -py; return sqrt(dx * dx + dy * dy); }; auto getClosestDist = [&](double x) -> double { int lo = 0, hi = N - 1; while (hi - lo > 3) { int mid = (lo + hi) / 2; if (stations[mid].first < x) lo = mid; else hi = mid; } double minD = DBL_MAX; for (int i = max(0, lo - 2); i <= min(N - 1, hi + 2); ++i) { minD = min(minD, dist(x, stations[i].first, stations[i].second)); } return minD; }; double l = 0, r = L; while (r - l > EPS) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; double d1 = getClosestDist(m1); double d2 = getClosestDist(m2); if (d1 < d2) l = m1; else r = m2; } double result = getClosestDist((l + r) / 2.0); cout << fixed << setprecision(10) << result << '\n'; 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...