Submission #1098020

#TimeUsernameProblemLanguageResultExecution timeMemory
10980200x34cMobile (BOI12_mobile)C++17
100 / 100
706 ms25384 KiB
#include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; /** * @return the intersection of the perpendicular line that * crosses the midpoint of Points a & b with the highway */ double max_point(const Point &a, const Point &b) { return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x); } /** @return the euclidean distance between points a & b */ double dist(const Point &a, const Point &b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } int main() { int n, l; cin >> n >> l; deque<Point> needed; for (int i = 0; i < n; i++) { Point cur; cin >> cur.x >> cur.y; cur.y = abs(cur.y); // always take the one with the lowest y coord if ((int)needed.size() && needed.back().x == cur.x) { if (cur.y >= needed.back().y) { continue; } else if (cur.y < needed.back().y) { needed.pop_back(); } } // find "crosses" while ((int)needed.size() > 1 && max_point(needed[(int)needed.size() - 2], needed.back()) > max_point(needed.back(), cur)) { needed.pop_back(); } needed.push_back(cur); } // out of bounds while ((int)needed.size() > 1 && max_point(needed[0], needed[1]) < 0) { needed.pop_front(); } while ((int)needed.size() > 1 && max_point(needed[(int)needed.size() - 2], needed.back()) > l) { needed.pop_back(); } double ans = 0; for (int x = 0; x < (int)needed.size(); x++) { // get critical points needed[x] is in charge of Point left = {0, 0}; Point right{l, 0}; if (x) { left.x = max_point(needed[x], needed[x - 1]); } if (x < (int)needed.size() - 1) { right.x = max_point(needed[x], needed[x + 1]); } if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) { continue; } ans = max({ans, dist(needed[x], left), dist(needed[x], right)}); } cout << fixed << setprecision(6) << ans << endl; }

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:63:15: warning: narrowing conversion of 'l' from 'int' to 'double' [-Wnarrowing]
   63 |   Point right{l, 0};
      |               ^
#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...