// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;
template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }
// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1E5 + 5;
constexpr db MAX = 2E9;
constexpr db EPS = 1E-10;
constexpr int PRECISION = 6;
struct Point {
db x, y;
Point() = default;
Point(db x, db y): x(x), y(y) {}
};
struct Interval {
db start, end;
Interval(db start, db end): start(start), end(end) {}
friend bool operator<(Interval const &a, Interval const &b) {
return a.start < b.start || (a.start == b.start && a.end < b.end);
}
};
Point points[N];
int n, L;
bool check(db r) {
vector<Interval> intervals;
FOR(i, 1, n) {
if (r < points[i].y) return false;
db d = sqrtl(sqr(r) - sqr(points[i].y));
intervals.emplace_back(points[i].x - d, points[i].x + d);
}
sort(all(intervals));
Interval merged = {0, 0};
for (auto const &interval : intervals) {
if (!merged.end) {
merged = interval;
} else if (merged.end < interval.start) { // there are disjoint intervals
return false;
} else {
chmax(merged.end, interval.end);
}
}
return merged.start <= 0 && merged.end >= L;
}
void solve() {
cin >> n >> L;
FOR(i, 1, n) {
db x, y;
cin >> x >> y;
points[i] = {x, y};
}
db l = 0, r = MAX, res = MAX;
while (r - l >= EPS) {
db m = (l + r) / 2;
if (check(m)) {
res = m;
r = m;
} else {
l = m;
}
}
cout << fixed << setprecision(PRECISION) << res << el;
}
int main() {
fast_io
#define LOCAL
#ifndef LOCAL
#define PROBLEM ""
freopen(PROBLEM ".INP", "r", stdin);
freopen(PROBLEM ".OUT", "w", stdout);
#endif
int t = 1;
// cin >> t;
while (t--) solve();
}
# | 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... |