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;
#define int long long
typedef long double ld;
int n, l;
ld inter (pair <int, int> &a, pair <int, int> &b) {
return 1.0 * (a.second - b.second) / (b.first - a.first);
}
const ld eps = 1e-9;
ld get (pair <int, int> &a, ld b, ld c) {
return max(b * b + a.first * b + a.second, c * c + a.first * c + a.second);
}
vector <pair <int, int>> dd;
deque <pair <int, int>> hull;
signed main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l;
cout << fixed << setprecision(9);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
int m = -2 * a;
int c = a * a + b * b;
dd.push_back({m, c});
}
sort(dd.begin(), dd.end());
int prev = -1e9 + 7;
for (auto i : dd) {
pair <int, int> x = i;
if (x.first == prev) continue;
prev = x.first;
if (hull.size() < 2) {
hull.push_front(x);
continue;
}
while (hull.size() >= 2) {
ld a = inter(hull[0], hull[1]), b = inter(x, hull[0]);
if (a + eps < b) {
hull.pop_front();
} else {
break;
}
}
hull.push_front(x);
}
while (hull.size() >= 2) {
if (inter(hull[0], hull[1]) < eps) hull.pop_front();
else break;
}
while (hull.size() >= 2) {
if (inter(hull.back(), hull[hull.size() - 2]) > l + eps) hull.pop_back();
else break;
}
ld ans = 0;
if (hull.size() == 1) {
ans = get(hull[0], 0, l);
cout << sqrt(ans) << '\n';
return 0;
}
ans = max(get(hull[0], 0, inter(hull[0], hull[1])), get(hull.back(), inter(hull.back(), hull[hull.size() - 2]), l));
for (int i = 1; i < (int)hull.size() - 1; i++) {
ans = max(ans, get(hull[i], inter(hull[i], hull[i - 1]), inter(hull[i], hull[i + 1])));
}
cout << sqrt(ans) << '\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... |