제출 #1294373

#제출 시각아이디문제언어결과실행 시간메모리
1294373sritthebossMobile (BOI12_mobile)C++20
4 / 100
1098 ms63820 KiB
#include "bits/stdc++.h" #define INF 1e18 using namespace std; bool test(int n, int l, double r, vector<pair<double, double>> stations) { vector<pair<double, double>> intervals; for (int i = 0; i < n; i++) { if (stations[i].second >= -r && stations[i].second <= r) { double x = stations[i].first; double y = stations[i].second; double lower = x - pow(pow(r, 2) - pow(y, 2), 0.5); double upper = x + pow(pow(r, 2) - pow(y, 2), 0.5); intervals.push_back({lower, upper}); } } stack<pair<double, double>> s; for (auto interval : intervals) { while (!s.empty() && s.top().second >= interval.first) { interval = {min(interval.first, s.top().first), max(interval.second, s.top().second)}; s.pop(); } s.push(interval); } if (s.size() == 1 && s.top().first <= 0 && s.top().second >= l) { return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, l; cin >> n >> l; vector<pair<double, double>> stations(n); for (int i = 0; i < n; i++) { cin >> stations[i].first >> stations[i].second; } long long lo = 0, hi = 1e12; while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (test(n, l, ((double) mid) / 10000, stations)) { hi = mid; } else { lo = mid + 1; } } cout << ((double) lo) / 10000 << endl; }
#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...