Submission #521937

#TimeUsernameProblemLanguageResultExecution timeMemory
521937sofapudenMobile (BOI12_mobile)C++14
100 / 100
835 ms35176 KiB
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); double k; int n; cin >> n >> k; vector<pair<double,double>> v(n); for(auto &x : v)cin >> x.first >> x.second; double l = 0, r = 2e9; while((r-l) > 0.0001){ double mid = (l+r)/2.0; vector<double> ran1, ran2; for(int i = 0; i < n; ++i){ if(abs(v[i].second) >= mid)continue; double z = sqrt(mid*mid-v[i].second*v[i].second); while(ran1.size() && max(v[i].first-z,0.0) < ran1.back()){ ran1.pop_back(); ran2.pop_back(); } if(ran1.empty() || v[i].first+z > ran2.back()){ if(ran1.size() && v[i].first-z < ran2.back()){ ran1.back() = max(0.0,min(v[i].first-z,ran1.back())); ran2.back() = min(v[i].first+z,k); } else{ ran1.push_back(max(min(v[i].first-z,k),0.0)); ran2.push_back(min(max(v[i].first+z,0.0),k)); } } if(ran1.back() == ran2.back()){ ran1.pop_back(); ran2.pop_back(); } } if(ran1.empty() || ran1[0] != 0 || ran2.back() != k){ l = mid; continue; } bool ok = 1; for(int i = 1; i < (int)ran1.size(); ++i){ if(ran2[i-1] < ran1[i]){ ok = 0; break; } if(ran2[i] == k)break; } if(ok){ r = mid; } else{ l = mid; } } printf("%.4f\n", l); }
#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...