oj.uz

Submission #936015

# Submission time Handle Problem Language Result Execution time Memory
936015 2024-03-01T01:32:58 Z cryan Mobile (BOI12_mobile) C++17
100 / 100
 850 ms 25352 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()

struct Point {
	double x, y;
};

/**
 * @returns the intersection of the perpendicular line that
 * crosses the midpoint of Points a & b with the highway
 */
double 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 - 2 * a.x);
}
/**
 * @returns the euclidean distance between Points a & b
 */
double dist(Point a, 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);

		// 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);
	}

	// out of bounds
	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;
}

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 348 KB Output is correct
3 Correct 1 ms 348 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 1 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 2 ms 348 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 484 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1328 KB Output is correct
2 Correct 54 ms 1308 KB Output is correct
3 Correct 38 ms 872 KB Output is correct
4 Correct 59 ms 1552 KB Output is correct
5 Correct 34 ms 868 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1108 KB Output is correct
2 Correct 46 ms 1116 KB Output is correct
3 Correct 63 ms 1292 KB Output is correct
4 Correct 60 ms 1616 KB Output is correct
5 Correct 75 ms 1872 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2384 KB Output is correct
2 Correct 66 ms 1548 KB Output is correct
3 Correct 55 ms 2388 KB Output is correct
4 Correct 85 ms 2132 KB Output is correct
5 Correct 56 ms 1180 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1876 KB Output is correct
2 Correct 82 ms 1720 KB Output is correct
3 Correct 61 ms 1616 KB Output is correct
4 Correct 89 ms 2140 KB Output is correct
5 Correct 70 ms 1632 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3192 KB Output is correct
2 Correct 70 ms 1692 KB Output is correct
3 Correct 60 ms 1568 KB Output is correct
4 Correct 84 ms 2384 KB Output is correct
5 Correct 70 ms 1620 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 12824 KB Output is correct
2 Correct 359 ms 8088 KB Output is correct
3 Correct 348 ms 7576 KB Output is correct
4 Correct 417 ms 9736 KB Output is correct
5 Correct 377 ms 7308 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 8588 KB Output is correct
2 Correct 368 ms 7748 KB Output is correct
3 Correct 314 ms 7504 KB Output is correct
4 Correct 434 ms 9748 KB Output is correct
5 Correct 390 ms 7568 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 15280 KB Output is correct
2 Correct 438 ms 9736 KB Output is correct
3 Correct 413 ms 8976 KB Output is correct
4 Correct 520 ms 12380 KB Output is correct
5 Correct 423 ms 8528 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 10132 KB Output is correct
2 Correct 424 ms 9088 KB Output is correct
3 Correct 363 ms 8272 KB Output is correct
4 Correct 511 ms 11916 KB Output is correct
5 Correct 438 ms 9296 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 17808 KB Output is correct
2 Correct 506 ms 11092 KB Output is correct
3 Correct 491 ms 10320 KB Output is correct
4 Correct 629 ms 13708 KB Output is correct
5 Correct 485 ms 9232 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 12164 KB Output is correct
2 Correct 490 ms 10440 KB Output is correct
3 Correct 449 ms 10632 KB Output is correct
4 Correct 589 ms 13592 KB Output is correct
5 Correct 511 ms 10388 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 20276 KB Output is correct
2 Correct 576 ms 12708 KB Output is correct
3 Correct 553 ms 11912 KB Output is correct
4 Correct 691 ms 16016 KB Output is correct
5 Correct 579 ms 11540 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 13704 KB Output is correct
2 Correct 560 ms 11788 KB Output is correct
3 Correct 523 ms 11712 KB Output is correct
4 Correct 694 ms 15700 KB Output is correct
5 Correct 595 ms 11860 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 25352 KB Output is correct
2 Correct 720 ms 15880 KB Output is correct
3 Correct 703 ms 14932 KB Output is correct
4 Correct 845 ms 19468 KB Output is correct
5 Correct 747 ms 14112 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 16904 KB Output is correct
2 Correct 699 ms 14540 KB Output is correct
3 Correct 650 ms 15444 KB Output is correct
4 Correct 850 ms 19588 KB Output is correct
5 Correct 733 ms 14928 KB Output is correct