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>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll
#define ld long double
#define pdd pair<ld, ld>
using namespace std;
int dist2(pii a, pii b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
ld dist(pii a, ld x)
{
return sqrt((((ld)a.first) - x) * (((ld)a.first) - x) + (ld)(a.second * a.second));
}
const int INF = 1e9 + 1;
const int INF2 = 1e12;
ld eps = 1e-4;
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, L;
cin >> N >> L;
vector<pii> inp(N);
map<int, int> closest;
for (int i = 0; i < N; i++)
{
int x, y;
cin >> x >> y;
inp[i] = {x, y};
if (!closest.count(x))
closest[x] = abs(y);
else
closest[x] = min(closest[x], abs(y));
}
vector<pii> pts;
for (pii p : closest)
pts.push_back(p);
N = pts.size();
vector<ld> bp(N);
for (int i = 0; i < N - 1; i++)
{
ld l = -INF, r = INF;
while ((r - l) > eps)
{
ld m = l + (r - l) / 2;
ld d1 = dist(pts[i], m), d2 = dist(pts[i + 1], m);
if (abs(d1 - d2) <= eps)
{
bp[i] = m;
break;
}
else if (d1 < d2)
l = m;
else
r = m;
}
}
ld mx_dist = 0;
for (int i = 0; i < N - 1; i++)
{
if (bp[i] < 0 || bp[i] > L)
continue;
mx_dist = max(mx_dist, dist(pts[i], bp[i]));
}
ld mn_start = INF2, mn_end = INF2;
for (int i = 0; i < N; i++)
{
mn_start = min(mn_start, dist(pts[i], 0));
mn_end = min(mn_end, dist(pts[i], L));
}
mx_dist = max({mx_dist, mn_start, mn_end});
cout << setprecision(4) << fixed << mx_dist << 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... |