Submission #1088606

#TimeUsernameProblemLanguageResultExecution timeMemory
1088606DaciejMaciejMobile (BOI12_mobile)C++17
100 / 100
382 ms41676 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld; template <class T> using VV = vector<vector<T>>; using VI = vector<int>; using VVI = vector<vector<int>>; using VL = vector<long long>; using VVL = vector<vector<long long>>; using VC = vector<char>; using VVC = vector<vector<char>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VD = vector<double>; using VVD = vector<vector<double>>; using PII = pair<int, int>; using PLL = pair<long long, long long>; using PIL = pair<int, long long>; using PLI = pair<long long, int>; using VPII = vector<pair<int, int>>; using VPLL = vector<pair<long long, long long>>; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (int(b)); i++) #define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() #define sq(a) ((a) * (a)) #define sz(x) ((int)x.size()) #define debug(x) cerr << #x << " = " << x << endl; // zero indexed template <class T> struct segtree { const T def = 0; int n; vector<T> seg; segtree(int _size) : n(_size), seg(2 * _size, def) {} T merge(T a, T b) { return max(a, b); } void update(int pos, T val) { for (seg[pos += n] = val; pos /= 2;) { seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]); } } T query(int l, int r) { // get [l, r] T a = def, b = def; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l % 2) a = merge(a, seg[l++]); if (r % 2) b = merge(b, seg[--r]); } return merge(a, b); } }; const ll MOD = 1e9 + 7; template <class T> void maxi(T &a, T b) { a = max(a, b); } template <class T> void mini(T &a, T b) { a = min(a, b); } template <class T> void addi(T &a, T b) { a = (a + b) % MOD; } template <class T> void subi(T &a, T b) { a = (a - b + MOD) % MOD; } template <class T> T add(T a, T b) { return (a + b) % MOD; } template <class T> T sub(T a, T b) { return (a - b + MOD) % MOD; } template <class T> T mul(T a, T b) { return ((a % MOD) * (b % MOD)) % MOD; } ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } const int INF = 1e9; const int MAX_N = 1e5 + 3; using LD = long double; struct P { LD x = 0; LD y = 0; }; LD mp(const P &a, const P &b) { return (sq(b.x) + sq(b.y) - sq(a.x) - sq(a.y)) / (2 * (b.x-a.x)); } LD dist(const P &a, const P &b) { return sqrt(sq(a.x-b.x) + sq(a.y-b.y)); } void solve() { int n, l; cin >> n >> l; deque<P> dq; FOR(i, 0, n) { P c; cin >> c.x >> c.y; c.y = abs(c.y); if(sz(dq) && dq.back().x == c.x) { if(c.y >= dq.back().y) continue; else { dq.pop_back(); } } while(sz(dq) >= 2 && mp(dq[sz(dq)-2], dq.back()) > mp(dq.back(), c)) { dq.pop_back(); } dq.push_back(c); } while(sz(dq) > 1 && mp(dq[0], dq[1]) < 0) dq.pop_front(); while(sz(dq) > 1 && mp(dq[sz(dq)-2], dq.back()) > l) dq.pop_back(); LD ans = 0; FOR(i, 0, sz(dq)) { P left, right; right.x = l; if(i) { left.x = mp(dq[i], dq[i-1]); } if(i < sz(dq) - 1) { right.x = mp(dq[i], dq[i+1]); } if(left.x < 0 || right.x > l || right.x < 0 || right.x > l) continue; ans = max({ans, dist(dq[i], left), dist(dq[i], right)}); } cout << fixed << setprecision(6) << ans << LINE; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); }
#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...