Submission #1215968

#TimeUsernameProblemLanguageResultExecution timeMemory
1215968newsboyMobile (BOI12_mobile)C++20
100 / 100
301 ms32500 KiB
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <map> #include <numeric> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <bitset> #include <queue> #include <deque> #include <stack> #include <cmath> #include <tuple> #include <cassert> #include <array> #include <list> #include <random> #include <initializer_list> using namespace std; using i64 = long long; using u64 = unsigned long long; using db = double; using ld = long double; constexpr i64 INF = 1E18; constexpr i64 MIN = -INF; constexpr i64 MAX = INF; constexpr int N = 1E4 + 10; struct Point { db x, y; }; db dist(Point& a, Point& b) { db dx = abs(a.x - b.x), dy = abs(a.y - b.y); return sqrt(dx * dx + dy * dy); } db calc(Point& a, Point& b) { return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * (b.x - a.x)); } void solve() { int n; db L; cin >> n >> L; vector<Point> points; for (int i = 0; i < n; ++i) { db x, y; cin >> x >> y; y = abs(y); if (!points.empty() && points.back().x == x) { if (points.back().y > y) { points.pop_back(); points.push_back({ x, y }); } } else { points.push_back({ x, y }); } } deque<Point> t; for (int i = 0; i < points.size(); ++i) { while (t.size() > 1 && calc(t[t.size() - 2], t[t.size() - 1]) >= calc(t[t.size() - 1], points[i])) { t.pop_back(); } t.push_back(points[i]); } while (t.size() > 1 && calc(t[0], t[1]) <= 0) { t.pop_front(); } while (t.size() > 1 && calc(t[t.size() - 2], t[t.size() - 1]) >= L) { t.pop_back(); } points.clear(); for (int i = 0; i < t.size(); ++i) { points.push_back(t[i]); } Point A = { 0, 0 }; Point B = { L, 0 }; db ans = max(dist(A, points[0]), dist(B, points.back())); for (int i = 1; i < points.size(); ++i) { Point tmp = { calc(points[i - 1], points[i]), 0 }; ans = max(ans, dist(points[i], tmp)); } cout << ans << '\n'; } //8 20 //2 2 //4 3 //5 2 //7 4 //10 5 //12 2 //16 3 //17 1 int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int t = 1; /*cin >> t;*/ while (t--) { solve(); } return 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...