This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ld> pld;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n, l;
cin >> n >> l;
vector<pld> arr(n);
for (auto &ref: arr) cin >> ref.first >> ref.second;
ld start = 0;
ld end = 1.42e9;
while (end - start > 1e-6) {
ld mid = start + (end - start) / 2;
bool check = false;
{
vector<pld> ranges;
for (int i = 0; i < n; i++) {
if (mid < arr[i].second) continue;
ld center = arr[i].first;
ld delta = sqrt(mid * mid - (ld) (arr[i].second * arr[i].second));
ranges.push_back({center - delta, center + delta});
}
if (ranges.empty()) {
check = false;
} else {
std::sort(ranges.begin(), ranges.end());
vector<pld> intersects;
for (auto& range : ranges) {
if (intersects.empty())
intersects.push_back(range);
else {
if (range.first <= intersects.back().second) {
intersects.back().second = max(intersects.back().second, range.second);
} else
intersects.push_back(range);
}
}
for (auto& seg : intersects) {
if ((seg.first <= (ld) 0) && ((ld) l <= seg.second)) {
check = true;
break;
}
}
}
}
if (check)
end = mid;
else
start = mid;
}
cout << fixed << setprecision(6) << start << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |