#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define eb emplace_back
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=1e6+10;
const int MAXL=5e2+10;
const int inf=1e17;
const int MOD=1e9+7;
typedef pair<double,double> pii;
typedef tuple<int,int,int> trio;
typedef tuple<int,int,int,int> squad;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,k,last[MAXN];
double l[MAXN],r[MAXN];
vector<pii> v;
double sq(double x){
return x*x;
}
int32_t main(){
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("cowrun.in","r",stdin);
//freopen("cowrun.out","w",stdout);
cin>>n>>k;
v.resize(n);
for(auto &[u,j]:v) cin>>u>>j;
l[0]=0,r[0]=k;
last[0]=-1;
fall(i,1,n-1){
int p=i-1;
while(p!=-1){
if(r[p]==-1) p=last[p];
else if(sq(l[p]-v[p].F)+sq(v[p].S)>sq(l[p]-v[i].F)+sq(v[i].S)){
l[i]=l[p],r[i]=k;
l[p]=r[p]=-1;
p=last[p];
}
else{
double ini=l[p],fim=k,ans=-1;
fall(_,1,40){
double mei=(ini+fim)/2.00;
if(sq(mei-v[p].F)+sq(v[p].S)>sq(mei-v[i].F)+sq(v[i].S)) ans=mei,fim=mei;
else ini=mei;
}
if(ans==-1) l[i]=r[i]=-1;
else{
l[i]=ans;
r[i]=k;
r[p]=ans;
last[i]=p;
}
break;
}
}
}
double ans=0;
fall(i,0,n-1){
if(r[i]==-1) continue;
ans=max(ans,sqrt(sq(l[i]-v[i].F)+sq(v[i].S)));
ans=max(ans,sqrt(sq(r[i]-v[i].F)+sq(v[i].S)));
}
cout.precision(6);
cout.setf(ios::fixed);
cout<<ans<<"\n";
}
# | 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... |