Submission #1098002

#TimeUsernameProblemLanguageResultExecution timeMemory
10980020x34cMobile (BOI12_mobile)C++17
50 / 100
1099 ms117916 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define endl '\n' #define int ll #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) { return sqrt((((ld)a.first) - x) * (((ld)a.first) - x) + (ld)(a.second * a.second)); } 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) { ld l = -1, r = INF; while ((r - l) > eps) { ld m = l + (r - l) / 2; ld d1 = dist(pts[idx1], m), d2 = dist(pts[idx2], m); if (d1 < d2) l = m; else r = m; } return l + (r - l) / 2LL; }; stack<int> stk; stk.push(0); vector<ld> dists, bps; for (int i = 1; i < N; i++) { ld bp = calc_bp(stk.top(), i); while (!bps.empty() && bps.back() > bp) { bps.pop_back(); stk.pop(); dists.pop_back(); bp = calc_bp(stk.top(), i); } bps.push_back(bp); dists.push_back(dist(pts[i], bp)); stk.push(i); } ld mx_dist = 0; for (int i = 0; i < 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], 0)); mn_end = min(mn_end, dist(pts[i], L)); } mx_dist = max({mx_dist, mn_start, mn_end}); cout << setprecision(4) << fixed << mx_dist << endl; }

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:92:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < 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...