Submission #1294128

#TimeUsernameProblemLanguageResultExecution timeMemory
1294128Jawad_Akbar_JJMobile (BOI12_mobile)C++20
100 / 100
489 ms31760 KiB
#include <iostream> #include <stack> #include <cmath> using namespace std; #define ld double const int N = 1<<20; ld x[N], y[N], xx[N], yy[N]; bool poss(int n, ld L, ld mid){ stack<pair<ld, ld>> stk; ld md = mid * mid; for (int i=1;i<=n;i++){ if (y[i] > mid) continue; ld b = -2 * x[i], c = xx[i] + yy[i] - md, sq = sqrtl(b * b - 4 * c); ld l = (-b - sq) * 0.5; ld r = (-b + sq) * 0.5; while (stk.size() > 0 and stk.top().first > l) r = max(r, stk.top().second), stk.pop(); if (stk.size() > 0 and stk.top().second >= l) l = stk.top().first, r = max(r, stk.top().second), stk.pop(); stk.push({l, r}); } while (stk.size() > 0){ auto [a, b] = stk.top(); stk.pop(); if (a <= 0 and b >= L) return 1; } return 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ld n, L; cin>>n>>L; for (int i=1;i<=n;i++){ int X, Y; cin>>X>>Y; x[i] = X; y[i] = abs(Y); if (i > 1 and x[i-1] == x[i] and y[i] < y[i-1]) swap(y[i], y[i-1]); if (i > 1 and x[i-1] == x[i] and y[i] >= y[i-1]) i--, n--; } for (int i=1;i<=n;i++) xx[i] = x[i] * x[i], yy[i] = y[i] * y[i]; ld l = 0, r = 3e9; while (l + 0.0001 < r){ ld mid = (l + r) * 0.5; if (poss(n, L, mid)) r = mid; else l = mid; } printf("%.5f\n", (double) r); }
#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...