oj.uz

Submission #1098020

# Submission time Handle Problem Language Result Execution time Memory
1098020 2024-10-08T19:54:31 Z 0x34c Mobile (BOI12_mobile) C++17
100 / 100
 706 ms 25384 KB 
#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> needed;
	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)needed.size() && needed.back().x == cur.x) {
			if (cur.y >= needed.back().y) {
				continue;
			} else if (cur.y < needed.back().y) {
				needed.pop_back();
			}
		}

		// find "crosses"
		while ((int)needed.size() > 1 &&
		       max_point(needed[(int)needed.size() - 2], needed.back()) >
		           max_point(needed.back(), cur)) {
			needed.pop_back();
		}

		needed.push_back(cur);
	}

	// out of bounds
	while ((int)needed.size() > 1 && max_point(needed[0], needed[1]) < 0) {
		needed.pop_front();
	}

	while ((int)needed.size() > 1 &&
	       max_point(needed[(int)needed.size() - 2], needed.back()) > l) {
		needed.pop_back();
	}

	double ans = 0;
	for (int x = 0; x < (int)needed.size(); x++) {
		// get critical points needed[x] is in charge of
		Point left = {0, 0};
		Point right{l, 0};

		if (x) { left.x = max_point(needed[x], needed[x - 1]); }
		if (x < (int)needed.size() - 1) {
			right.x = max_point(needed[x], needed[x + 1]);
		}

		if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) { continue; }

		ans = max({ans, dist(needed[x], left), dist(needed[x], right)});
	}

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

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1108 KB Output is correct
2 Correct 51 ms 1360 KB Output is correct
3 Correct 26 ms 856 KB Output is correct
4 Correct 45 ms 1364 KB Output is correct
5 Correct 20 ms 600 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1104 KB Output is correct
2 Correct 35 ms 1116 KB Output is correct
3 Correct 42 ms 1360 KB Output is correct
4 Correct 65 ms 1620 KB Output is correct
5 Correct 56 ms 1872 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2388 KB Output is correct
2 Correct 48 ms 1432 KB Output is correct
3 Correct 42 ms 2484 KB Output is correct
4 Correct 71 ms 2216 KB Output is correct
5 Correct 42 ms 1104 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1872 KB Output is correct
2 Correct 75 ms 1616 KB Output is correct
3 Correct 44 ms 1620 KB Output is correct
4 Correct 75 ms 2128 KB Output is correct
5 Correct 52 ms 1616 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2896 KB Output is correct
2 Correct 53 ms 1620 KB Output is correct
3 Correct 46 ms 1616 KB Output is correct
4 Correct 71 ms 2136 KB Output is correct
5 Correct 52 ms 1620 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 12484 KB Output is correct
2 Correct 321 ms 7824 KB Output is correct
3 Correct 277 ms 7248 KB Output is correct
4 Correct 347 ms 9296 KB Output is correct
5 Correct 295 ms 6764 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 8068 KB Output is correct
2 Correct 308 ms 7296 KB Output is correct
3 Correct 232 ms 7508 KB Output is correct
4 Correct 404 ms 9044 KB Output is correct
5 Correct 293 ms 7160 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 15328 KB Output is correct
2 Correct 341 ms 8900 KB Output is correct
3 Correct 322 ms 8272 KB Output is correct
4 Correct 420 ms 11344 KB Output is correct
5 Correct 333 ms 8020 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 9556 KB Output is correct
2 Correct 324 ms 8648 KB Output is correct
3 Correct 294 ms 7840 KB Output is correct
4 Correct 423 ms 11088 KB Output is correct
5 Correct 375 ms 8532 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 17380 KB Output is correct
2 Correct 512 ms 10376 KB Output is correct
3 Correct 379 ms 9712 KB Output is correct
4 Correct 540 ms 12500 KB Output is correct
5 Correct 376 ms 8788 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 10804 KB Output is correct
2 Correct 388 ms 10068 KB Output is correct
3 Correct 396 ms 9936 KB Output is correct
4 Correct 487 ms 12628 KB Output is correct
5 Correct 421 ms 9808 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 20148 KB Output is correct
2 Correct 478 ms 11920 KB Output is correct
3 Correct 431 ms 11412 KB Output is correct
4 Correct 608 ms 15016 KB Output is correct
5 Correct 461 ms 10892 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 12624 KB Output is correct
2 Correct 462 ms 11348 KB Output is correct
3 Correct 404 ms 11492 KB Output is correct
4 Correct 533 ms 14608 KB Output is correct
5 Correct 493 ms 11408 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 25384 KB Output is correct
2 Correct 591 ms 15880 KB Output is correct
3 Correct 553 ms 14872 KB Output is correct
4 Correct 706 ms 19540 KB Output is correct
5 Correct 579 ms 14244 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 15568 KB Output is correct
2 Correct 552 ms 13676 KB Output is correct
3 Correct 501 ms 14416 KB Output is correct
4 Correct 686 ms 17748 KB Output is correct
5 Correct 658 ms 14168 KB Output is correct