This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef pair<double,double> S;
S seg(pl a, double rad) {
if(a.second > rad) {return {a.second,a.second};}
double r = sqrt(rad*rad-a.second*a.second);
return {a.first-r,a.first+r};
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n,len;
cin >> n >> len;
vpl w;
for(int i=0;i<n;i++) {
ll a,b;
cin >> a >> b;
b = abs(b);
w.emplace_back(a,b);
}
double st = 0;
double ed = 4e9;
double ls = ed;
for(int iter=0;iter<45;iter++) {
double m = (st+ed)/2;
stack<S> sto;
bool poss = false;
for(int i=0;i<n;i++) {
if(poss) {break;}
if(m > w[i].second) {
S se = seg(w[i],m);
while(!sto.empty() && sto.top().second > se.first) {
se.first = min(se.first,sto.top().first);
se.second = max(se.second,sto.top().second);
sto.pop();
}
if(se.first <= 0 && se.second >= len) {
poss = true;
break;
}
sto.push(se);
}
}
if(poss) {
ls = m;
ed = m;
} else {
st = m;
}
}
cout << fixed << setprecision(7) << ls << '\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... |