oj.uz

Submission #935546

# Submission time Handle Problem Language Result Execution time Memory
935546 2024-02-29T09:00:58 Z cryan Mobile (BOI12_mobile) C++17
100 / 100
 443 ms 33184 KB 
// 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

#define double long double
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));
		return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x);
	};

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

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

		// take the one with the lowest y coord
		if (sz(stck) && 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 (sz(stck) > 1 && max_point(stck[sz(stck) - 2], stck.back()) > max_point(stck.back(), cur)) {
			stck.pop_back();
		}

		stck.push_back(cur);
	}

	while (sz(stck) > 1 && max_point(stck[0], stck[1]) < 0)
		stck.pop_front();
	while (sz(stck) > 1 && max_point(stck[sz(stck) - 2], stck.back()) > l)
		stck.pop_back();

	double ans = 0;
	for (int x = 0; x < sz(stck); x++) {
		Point left = {(x ? max_point(stck[x], stck[x - 1]) : 0), 0};
		Point right = {(x < sz(stck) - 1 ? max_point(stck[x], stck[x + 1]) : l), 0};
		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;
}

// 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.)

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 536 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 540 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 604 KB Output is correct
2 Correct 29 ms 344 KB Output is correct
3 Correct 19 ms 472 KB Output is correct
4 Correct 31 ms 476 KB Output is correct
5 Correct 15 ms 836 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 344 KB Output is correct
2 Correct 32 ms 1052 KB Output is correct
3 Correct 36 ms 1208 KB Output is correct
4 Correct 36 ms 1304 KB Output is correct
5 Correct 37 ms 1360 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3164 KB Output is correct
2 Correct 38 ms 1196 KB Output is correct
3 Correct 31 ms 3672 KB Output is correct
4 Correct 45 ms 2236 KB Output is correct
5 Correct 30 ms 1360 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 348 KB Output is correct
2 Correct 35 ms 348 KB Output is correct
3 Correct 30 ms 848 KB Output is correct
4 Correct 48 ms 708 KB Output is correct
5 Correct 42 ms 476 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2396 KB Output is correct
2 Correct 35 ms 348 KB Output is correct
3 Correct 37 ms 860 KB Output is correct
4 Correct 43 ms 472 KB Output is correct
5 Correct 38 ms 468 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 16996 KB Output is correct
2 Correct 166 ms 4744 KB Output is correct
3 Correct 158 ms 4176 KB Output is correct
4 Correct 220 ms 5352 KB Output is correct
5 Correct 198 ms 4052 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 460 KB Output is correct
2 Correct 203 ms 5756 KB Output is correct
3 Correct 155 ms 6480 KB Output is correct
4 Correct 225 ms 5340 KB Output is correct
5 Correct 219 ms 4208 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 20136 KB Output is correct
2 Correct 196 ms 5456 KB Output is correct
3 Correct 190 ms 9008 KB Output is correct
4 Correct 272 ms 12204 KB Output is correct
5 Correct 261 ms 8240 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 448 KB Output is correct
2 Correct 227 ms 6228 KB Output is correct
3 Correct 177 ms 6052 KB Output is correct
4 Correct 271 ms 12116 KB Output is correct
5 Correct 238 ms 9040 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 23248 KB Output is correct
2 Correct 233 ms 6224 KB Output is correct
3 Correct 221 ms 10576 KB Output is correct
4 Correct 317 ms 14008 KB Output is correct
5 Correct 265 ms 9300 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 696 KB Output is correct
2 Correct 271 ms 7152 KB Output is correct
3 Correct 217 ms 8784 KB Output is correct
4 Correct 351 ms 13636 KB Output is correct
5 Correct 282 ms 10440 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 26688 KB Output is correct
2 Correct 259 ms 7012 KB Output is correct
3 Correct 258 ms 12076 KB Output is correct
4 Correct 355 ms 16048 KB Output is correct
5 Correct 330 ms 11732 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 600 KB Output is correct
2 Correct 304 ms 7908 KB Output is correct
3 Correct 244 ms 9556 KB Output is correct
4 Correct 355 ms 15828 KB Output is correct
5 Correct 317 ms 12136 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 33184 KB Output is correct
2 Correct 320 ms 8492 KB Output is correct
3 Correct 316 ms 14904 KB Output is correct
4 Correct 437 ms 19672 KB Output is correct
5 Correct 392 ms 14272 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 344 KB Output is correct
2 Correct 381 ms 9456 KB Output is correct
3 Correct 317 ms 11856 KB Output is correct
4 Correct 443 ms 10688 KB Output is correct
5 Correct 409 ms 8408 KB Output is correct