Submission #935320

#	Time	Username	Problem	Language	Result	Execution time	Memory
935320		cryan	Mobile (BOI12_mobile)	C++17	0 / 100	367 ms	34120 KiB

mobile

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl '\n'
#endif

struct Point {
	double x, y;
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, l;
	cin >> n >> l;

	function<double(Point, Point)> max_point = [&](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));
	};

	function<double(Point, Point)> dist = [&](Point a, Point b) {
		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	};

	vector<Point> stck(n);
	vector<Point> todo;
	int idx = 0;
	for (int i = 0; i < n; i++) {
		Point cur;
		cin >> cur.x >> cur.y;
		cur.y = abs(cur.y);

		// directly above
		if (idx && stck[idx - 1].x == cur.x && cur.y < stck[idx - 1].y) {
			idx--;
		}

		while (idx > 1 && todo.back().x > max_point(stck[idx - 1], cur)) {
			idx--;
			todo.pop_back();
		}

		stck[idx] = cur;
		if (idx) {
			todo.push_back(Point{max_point(stck[idx - 1], cur), 0});
		}

		idx++;
	}
	// cout << todo << endl;
	// cout << stck << endl;

	Point endpt = {l, 0};
	double ans = max(dist(todo[0], Point({0, 0})), dist(stck[0], todo[0]));
	ans = max({ans, dist(todo.back(), endpt), dist(todo.back(), stck[idx - 1])});
	for (int x = 1; x < sz(todo) - 1; x++) {
		ans = max({ans, dist(todo[x], stck[x]), dist(todo[x], stck[x - 1])});
	}

	cout << fixed << setprecision(6) << ans << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:67:17: warning: narrowing conversion of 'l' from 'int' to 'double' [-Wnarrowing]
   67 |  Point endpt = {l, 0};
      |                 ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5