this 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.
code
include
include
include
include
include
include
include <stdio.h>
include
include
include
include
include
include
include
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
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
define ld long double
define pld pair<ld,ld>
const ld INF = 1e9+10; using namespace std; const int MAXN = 1000*1000+10;
vector allP;
bool check(ld dist,ld l){ deque 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;
}