Submission #1194607

#TimeUsernameProblemLanguageResultExecution timeMemory
1194607cpismylifeOwOMobile (BOI12_mobile)C++20
32 / 100
1097 ms69304 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; const int MaxN = 1e6 + 5; int n; long long l; pair<long long, long long> arr[MaxN]; void Inp() { cin >> n >> l; for (int x = 1; x <= n; x++) { cin >> arr[x].first >> arr[x].second; } } bool Check(long double k) { vector<long double> in, out; int cur = 0; for (int x = 1; x <= n; x++) { if (abs(arr[x].second) >= k) { cur++; continue; } long double p = sqrtl(k * k - arr[x].second * arr[x].second); if (arr[x].first - p >= 0) { in.push_back(0); out.push_back((long double)arr[x].first - p); } if (arr[x].first + p <= l) { in.push_back((long double)arr[x].first + p); out.push_back(l); } } sort(in.begin(), in.end()); sort(out.begin(), out.end()); reverse(in.begin(), in.end()); reverse(out.begin(), out.end()); while (!in.empty() || !out.empty()) { long double p = 0; if (out.empty() || (!in.empty() && in.back() < out.back())) { p = in.back(); } else { p = out.back(); } while (!in.empty() && in.back() == p) { cur++; in.pop_back(); } if (cur == n) { return true; } while (!out.empty() && out.back() == p) { cur--; out.pop_back(); } } return false; } void Exc() { long long l = 0, r = 1e18, mid, res = 0; while (l <= r) { mid = (l + r) / 2; if (Check((long double)((long double)mid / 100000.0))) { res = mid; l = mid + 1; } else { r = mid - 1; } } cout << fixed << setprecision(5) << (long double)((long double)res / 100000.0); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int test = 1; //cin >> test; for (int x = 1; x <= test; x++) { Inp(); Exc(); } 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...