Submission #916293

#TimeUsernameProblemLanguageResultExecution timeMemory
916293asdasdqwerMobile (BOI12_mobile)C++14
8 / 100
1066 ms66284 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define pii array<int,2> #define double long double signed main() { ios::sync_with_stdio(false); cin.tie(0); int n,t;cin>>n>>t; vector<pii> v(n); for (auto &x:v)cin>>x[0]>>x[1]; double l = 1; double r = 1e15; vector<bool> rem(n, false); while (abs(l-r) > 0.00001) { double m = (l+r)/2.0; int i=0; vector<array<double,2>> start; for (auto &x:v) { if ((double)abs(x[1]) >= m) { rem[i]=true; } else { double aa=(double)abs(x[1]); double dis=sqrt(m*m-aa*aa); array<double,2> pos1 = {x[0]-dis,x[0]+dis}; if ((pos1[0] < 0.0 && pos1[1] < 0.0) || (pos1[0] > (double)t && pos1[1] > (double)t)) { rem[i]=true; } else { pos1[0]=max(pos1[0], (double)0.0); pos1[1]=min(pos1[1], (double)t); start.push_back(pos1); } } i++; } start.push_back({0.0, 0.0}); start.push_back({(double)t,(double)t}); sort(start.begin(),start.end()); // cout<<m<<" "<<l<<" "<<r<<"\n"; // for (auto &x:start) { // cout<<x[0]<<" "<<x[1]<<"\n"; // } // cout<<"\n"; // for (auto &x:v) { // cout<<x[0]<<" "<<x[1]<<"\n"; // } // cout<<"\n\n"; array<double,2> pos={0.0, 0.0}; bool possible=true; for (auto &x:start) { if (x[0] <= pos[1]) { pos[1]=max(pos[1], x[1]); } else { possible=false; break; } } if (possible) { r=m; // int cnt=0; // int pt=0; // for (int i=0;i<n;i++) { // if (rem[i]) { // cnt++; // } // else if (cnt != 0) { // swap(v[i], v[pt]); // } // if (!rem[i]) { // pt++; // } // } // n -= cnt; // while (v.size() != n){ // v.pop_back(); // rem.pop_back(); // } // for (int i=0;i<n;i++) { // rem[i]=false; // } } else { l=m; for (i=0;i<n;i++) { rem[i]=false; } } } r = round(r * 10000.0) / 10000.0; cout<<r<<"\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...