#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
#define ld double
const int N = 1<<20;
ld x[N], y[N], xx[N], yy[N];
bool poss(int n, ld L, ld mid){
stack<pair<ld, ld>> stk;
ld md = mid * mid;
for (int i=1;i<=n;i++){
if (y[i] > mid)
continue;
ld b = -2 * x[i], c = xx[i] + yy[i] - md, sq = sqrtl(b * b - 4 * c);
ld l = (-b - sq) * 0.5;
ld r = (-b + sq) * 0.5;
while (stk.size() > 0 and stk.top().first > l)
r = max(r, stk.top().second), stk.pop();
if (stk.size() > 0 and stk.top().second >= l)
l = stk.top().first, r = max(r, stk.top().second), stk.pop();
stk.push({l, r});
}
while (stk.size() > 0){
auto [a, b] = stk.top();
stk.pop();
if (a <= 0 and b >= L)
return 1;
}
return 0;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ld n, L;
cin>>n>>L;
for (int i=1;i<=n;i++){
int X, Y;
cin>>X>>Y;
x[i] = X;
y[i] = abs(Y);
if (i > 1 and x[i-1] == x[i] and y[i] < y[i-1])
swap(y[i], y[i-1]);
if (i > 1 and x[i-1] == x[i] and y[i] >= y[i-1])
i--, n--;
}
for (int i=1;i<=n;i++)
xx[i] = x[i] * x[i], yy[i] = y[i] * y[i];
ld l = 0, r = 3e9;
while (l + 0.0001 < r){
ld mid = (l + r) * 0.5;
if (poss(n, L, mid))
r = mid;
else
l = mid;
}
printf("%.5f\n", (double) r);
}
| # | 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... |