Submission #916385

#TimeUsernameProblemLanguageResultExecution timeMemory
916385asdasdqwerMobile (BOI12_mobile)C++14
4 / 100
1063 ms82236 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define int int64_t #define pii array<int,2> 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]; vector<pii> tt; for (auto &x:v) { if (!tt.size()) { tt.push_back(x); } else if (tt.back()[0] == x[0] && abs(tt.back()[1]) > abs(x[1])) { tt.pop_back(); } tt.push_back(x); } v=tt; n=v.size(); long double l = 1; long double r = 1e10; cout<<setprecision(15); for (auto &x:v) { r = min(r, (long double)max(sqrt(x[0]*x[0] + x[1]*x[1]), sqrt((x[0]-t)*(x[0]-t) + x[1]*x[1]))); } // cout<<r<<"\n"; vector<bool> rem(n, false); while (abs(l-r) > 0.0001) { long double m = (l+r)/2.0; int i=0; vector<array<long double,2>> start; bool all=false; for (auto &x:v) { if ((double)abs(x[1]) >= m) { rem[i]=true; } // if (rem[i]) { // i++; // continue; // } else { long double aa=(double)abs(x[1]); long double dis=sqrt(m*m-aa*aa); array<long 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], (long double)0.0); pos1[1]=min(pos1[1], (long double)t); if (pos1[0] == 0.0 && pos1[1] == t) { all=true; break; } start.push_back(pos1); } } i++; } if (all) { r=m; continue; } bool possible=true; stack<double> ss; for (auto &x:start) { while (ss.size() && ss.top() >= x[0])ss.pop(); ss.push(x[1]); } while (ss.size()) { if (ss.top() != t) { possible=false; break; } ss.pop(); } 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; // } } } 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...