Submission #1197702

#TimeUsernameProblemLanguageResultExecution timeMemory
1197702cpismylifeOwOMobile (BOI12_mobile)C++20
25 / 100
1098 ms31876 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; const int MaxN = 1e6 + 5; int n; long double l; pair<long double, long double> arr[MaxN]; void Inp() { cin >> n >> l; for (int x = 1; x <= n; x++) { cin >> arr[x].first >> arr[x].second; } sort(arr + 1, arr + n + 1); } stack<pair<long double, long double>> st; bool Check(long double k) { while (!st.empty()) { st.pop(); } for (int x = 1; x <= n; x++) { if (arr[x].second > k) { continue; } long double p = sqrt(k * k - arr[x].second * arr[x].second), l = arr[x].first - p, r = arr[x].first + p; while (!st.empty() && max(l, st.top().first) <= min(r, st.top().second)) { l = min(l, st.top().first); r = max(r, st.top().second); st.pop(); } st.push(make_pair(l, r)); } while (!st.empty()) { if (st.top().first <= 0 && l <= st.top().second) { return true; } st.pop(); } return false; } void Exc() { long double l = 0, r = 1e10, mid, res = 0; while (r - l > 1e-3) { mid = (l + r) / 2.0; if (Check(mid)) { res = mid; r = mid; } else { l = mid; } } cout << fixed << setprecision(3) << res; } 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...