제출 #481867

#제출 시각아이디문제언어결과실행 시간메모리
481867wwddMobile (BOI12_mobile)C++14
100 / 100
445 ms16948 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...