[this](https://cses.fi/file/c76360487d6e9489e00da88645a49edb20da5126f8dc5cafd19bafd14068179d) is the pdf link, see p2 (mobiles). ↵
↵
SOLUTION : binsrch on answer and check. however my code is giving error. its quite small, so hopefully it will be readable.↵
↵
↵
~~~~~↵
↵
<spoiler summary="code">↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <iomanip>↵
#include <algorithm>↵
#include <functional>↵
#include <stdio.h>↵
#include <cmath>↵
#include <queue>↵
#include <string>↵
#include <map>↵
#include <complex>↵
#include <stack>↵
#include <set>↵
↵
#define FOR(i,n) for(int i=0;i<n;i++)↵
#define FORE(i,a,b) for(int i=a;i<=b;i++)↵
#define ll long long int↵
#define vi vector<int>↵
#define ii pair<int,int>↵
#define pb push_back↵
#define mp make_pair↵
#define ff first↵
#define ss second↵
#define pll pair<ll,ll>↵
#define cd complex<double> ↵
#define ld long double↵
#define pld pair<ld,ld>↵
↵
const ld INF = 1e9+10;↵
using namespace std;↵
const int MAXN = 1000*1000+10;↵
↵
vector<pld> allP;↵
↵
bool check(ld dist,ld l){↵
deque<pld> dq;↵
for(auto e : allP){↵
ld dd = dist*dist — e.ss*e.ss;↵
if(dd < 0)continue;↵
dd = sqrt(dd);↵
pld r = {e.ff-dd,e.ff+dd};↵
while(dq.size() > 0 and dq.back().ff >= r.ff)↵
dq.pop_back();↵
dq.pb(r);↵
}↵
if(dq.empty())return 0;↵
if(dq.front().ff > 0)return 0;↵
ld right = dq[0].ss;↵
FORE(i,1,(int)dq.size()-1){↵
if(dq[i].ff > dq[i-1].ss)return 0;↵
right = max(right,dq[i].ss);↵
}↵
return right >= l;↵
}↵
↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n,l;↵
cin >> n >> l;↵
FOR(i,n){↵
int a,b;↵
cin >> a >> b;↵
allP.pb({a,abs(b)});↵
}↵
ld lo = 0;↵
ld hi = 3e9;↵
ld best = 1e12;↵
while(lo <= hi){↵
if(hi-lo < 1e-5){↵
break;↵
}↵
ld mid = (lo+hi)/2;↵
if(check(mid,l)){↵
best = min(best,mid);↵
hi = mid;↵
}else{↵
lo = mid;↵
}↵
}↵
printf("%.5f\n",(double)best);↵
return 0;↵
}↵
</spoiler>↵
↵
~~~~~↵
↵
↵
SOLUTION : binsrch on answer and check. however my code is giving error. its quite small, so hopefully it will be readable.↵
↵
~~~~~↵
↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <iomanip>↵
#include <algorithm>↵
#include <functional>↵
#include <stdio.h>↵
#include <cmath>↵
#include <queue>↵
#include <string>↵
#include <map>↵
#include <complex>↵
#include <stack>↵
#include <set>↵
↵
#define FOR(i,n) for(int i=0;i<n;i++)↵
#define FORE(i,a,b) for(int i=a;i<=b;i++)↵
#define ll long long int↵
#define vi vector<int>↵
#define ii pair<int,int>↵
#define pb push_back↵
#define mp make_pair↵
#define ff first↵
#define ss second↵
#define pll pair<ll,ll>↵
#define cd complex<double> ↵
#define ld long double↵
#define pld pair<ld,ld>↵
↵
const ld INF = 1e9+10;↵
using namespace std;↵
const int MAXN = 1000*1000+10;↵
↵
vector<pld> allP;↵
↵
bool check(ld dist,ld l){↵
deque<pld> dq;↵
for(auto e : allP){↵
ld dd = dist*dist — e.ss*e.ss;↵
if(dd < 0)continue;↵
dd = sqrt(dd);↵
pld r = {e.ff-dd,e.ff+dd};↵
while(dq.size() > 0 and dq.back().ff >= r.ff)↵
dq.pop_back();↵
dq.pb(r);↵
}↵
if(dq.empty())return 0;↵
if(dq.front().ff > 0)return 0;↵
ld right = dq[0].ss;↵
FORE(i,1,(int)dq.size()-1){↵
if(dq[i].ff > dq[i-1].ss)return 0;↵
right = max(right,dq[i].ss);↵
}↵
return right >= l;↵
}↵
↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n,l;↵
cin >> n >> l;↵
FOR(i,n){↵
int a,b;↵
cin >> a >> b;↵
allP.pb({a,abs(b)});↵
}↵
ld lo = 0;↵
ld hi = 3e9;↵
ld best = 1e12;↵
while(lo <= hi){↵
if(hi-lo < 1e-5){↵
break;↵
}↵
ld mid = (lo+hi)/2;↵
if(check(mid,l)){↵
best = min(best,mid);↵
hi = mid;↵
}else{↵
lo = mid;↵
}↵
}↵
printf("%.5f\n",(double)best);↵
return 0;↵
}↵
</spoiler>↵
↵
↵
