#include <bits/stdc++.h>
using namespace std;
struct Point {
long long x, y;
};
int count_, length;
vector<Point> points;
pair<double, double> merge(pair<double, double> first, pair<double, double> second) {
if (second < first) swap(first, second);
if (first.second < second.first) {
return make_pair(-1.0, -1.0);
}
return make_pair(first.first, max(first.second, second.second));
}
bool works(double distance) {
stack<pair<double, double>> stack;
for (Point point: points) {
double x_change_squared = distance * distance - point.y * point.y;
if (x_change_squared < 0) {
continue;
}
pair<double, double> interval = make_pair(point.x - sqrt(x_change_squared), point.x + sqrt(x_change_squared));
while (!stack.empty()) {
pair<double, double> result = merge(stack.top(), interval);
if (result == make_pair(-1.0, -1.0)) break;
stack.pop();
interval = result;
}
stack.emplace(interval);
}
while (!stack.empty()) {
pair<double, double> interval = stack.top();
stack.pop();
if (interval.first <= 0 && length <= interval.second) {
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> count_ >> length;
points.resize(count_);
for (int index = 0; index < count_; index++) cin >> points[index].x >> points[index].y;
double left = 1, right = 1.5e9;
while (right - left > 1e-3) {
double middle = (left + right) / 2;
if (works(middle)) {
right = middle;
}
else {
left = middle;
}
}
cout << fixed << setprecision(4) << left << "\n";
return 0;
}
# | 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... |