Submission #1098024

#TimeUsernameProblemLanguageResultExecution timeMemory
10980240x34cMobile (BOI12_mobile)C++17
100 / 100
546 ms114728 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define endl '\n' #define ld long double #define pdd pair<ld, ld> using namespace std; int dist2(pii a, pii b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); } ld dist(pii a, ld x) { ld x1 = a.first, y = a.second; return sqrt((x1 - x) * (x1 - x) + y * y); } const int INF2 = 1e12; const int INF = 1e9 + 1; ld eps = 1e-4; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, L; cin >> N >> L; vector<pii> inp(N); map<int, int> closest; for (int i = 0; i < N; i++) { int x, y; cin >> x >> y; inp[i] = {x, y}; if (!closest.count(x)) closest[x] = y; else closest[x] = (abs(closest[x]) > abs(y) ? y : closest[x]); } vector<pii> pts; for (pii p : closest) pts.push_back(p); N = pts.size(); auto calc_bp = [&](int idx1, int idx2) { try { ld x1 = pts[idx1].first, y1 = pts[idx1].second; ld x2 = pts[idx2].first, y2 = pts[idx2].second; if (x1 - x2 == 0) return (ld)-1; return ((ld)0.5) * (x1 + x2 + (y1 * y1 - y2 * y2) / (x1 - x2)); } catch (const std::exception &e) { return (ld)-1; } }; stack<int> stk; stk.push(0); vector<ld> dists, bps; for (int i = 1; i < N; i++) { try { ld bp = calc_bp(stk.top(), i); bool emp = false; while (!bps.empty() && bps.back() >= bp) { bps.pop_back(); stk.pop(); dists.pop_back(); if (stk.empty()) emp = true; else bp = calc_bp(stk.top(), i); } if (!emp) { bps.push_back(bp); dists.push_back(dist(pts[i], bp)); } stk.push(i); } catch (const std::exception &e) { } } ld mx_dist = 0; for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++) { if (bps[i] < 0 || bps[i] > L) continue; mx_dist = max(mx_dist, dists[i]); } ld mn_start = INF2, mn_end = INF2; for (int i = 0; i < N; i++) { mn_start = min(mn_start, dist(pts[i], (ld)0)); mn_end = min(mn_end, dist(pts[i], (ld)L)); } mx_dist = max({mx_dist, mn_start, mn_end}); cout << setprecision(4) << fixed << mx_dist << endl; }

Compilation message (stderr)

mobile.cpp:21:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   21 | const int INF2 = 1e12;
      |                  ^~~~
mobile.cpp: In function 'int main()':
mobile.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  105 |     for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...