Submission #936069

#	Time	Username	Problem	Language	Result	Execution time	Memory
936069		cryan	Mobile (BOI12_mobile)	C++17	100 / 100	856 ms	25360 KiB

mobile

#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> stck;
	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)stck.size() && stck.back().x == cur.x) {
			if (cur.y >= stck.back().y) {
				continue;
			} else if (cur.y < stck.back().y) {
				stck.pop_back();
			}
		}
 
		// find "crosses"
		while ((int)stck.size() > 1 && max_point(stck[(int)stck.size() - 2], stck.back()) > max_point(stck.back(), cur)) {
			stck.pop_back();
		}
 
		stck.push_back(cur);
	}
 
	// out of bounds
	while ((int)stck.size() > 1 && max_point(stck[0], stck[1]) < 0) {
		stck.pop_front();
	}
 
	while ((int)stck.size() > 1 && max_point(stck[(int)stck.size() - 2], stck.back()) > l) {
		stck.pop_back();
	}
 
	double ans = 0;
	for (int x = 0; x < (int)stck.size(); x++) {
		// get critical points stck[x] is in charge of 
		Point left = {0, 0};
		Point right {l, 0};
 
		if (x) { left.x = max_point(stck[x], stck[x - 1]); }
		if (x < (int)stck.size() - 1) { right.x = max_point(stck[x], stck[x + 1]); }
 
		if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) { continue; }
 
		ans = max({ans, dist(stck[x], left), dist(stck[x], right)});
	}
 
	cout << fixed << setprecision(6) << ans << endl;
}

Compilation message (stderr)

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

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