제출 #1196249

#제출 시각아이디문제언어결과실행 시간메모리
1196249cpismylifeOwOMobile (BOI12_mobile)C++20
50 / 100
1096 ms31752 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; } } bool Check(long double k) { vector<pair<long double, long double>> now; now.push_back(make_pair(0, l)); for (int x = 1; x <= n; x++) { if (abs(arr[x].second) >= k) { continue; } long double p = sqrtl(k * k - arr[x].second * arr[x].second); vector<pair<long double, long double>> add; if (arr[x].first - p >= 0.0) { add.push_back(make_pair(0, min((long double)arr[x].first - p, l))); } if (arr[x].first + p <= l) { add.push_back(make_pair(max((long double)arr[x].first + p, (long double)0), l)); } vector<pair<long double, long double>> tmp = now; now.clear(); for (pair<long double, long double>& x : tmp) { for (pair<long double, long double>& y : add) { long double l = max(x.first, y.first), r = min(x.second, y.second); if (l <= r) { now.push_back(make_pair(l, r)); } } } } return !now.empty(); } void Exc() { long double l = 0, r = 1e14, mid, res = 0; while (r - l > 1e-5) { mid = (l + r) / 2.0; if (Check(mid)) { res = mid; l = mid; } else { r = mid; } } cout << fixed << setprecision(5) << 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...