oj.uz

Submission #936069

# Submission time Handle Problem Language Result Execution time Memory
936069 2024-03-01T05:50:53 Z cryan Mobile (BOI12_mobile) C++17
100 / 100
 856 ms 25360 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> 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

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.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 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 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 5 ms 348 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 3 ms 348 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 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1276 KB Output is correct
2 Correct 54 ms 1364 KB Output is correct
3 Correct 34 ms 860 KB Output is correct
4 Correct 60 ms 1372 KB Output is correct
5 Correct 29 ms 604 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1156 KB Output is correct
2 Correct 47 ms 1112 KB Output is correct
3 Correct 58 ms 1364 KB Output is correct
4 Correct 59 ms 1616 KB Output is correct
5 Correct 71 ms 1808 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2480 KB Output is correct
2 Correct 57 ms 1360 KB Output is correct
3 Correct 54 ms 2384 KB Output is correct
4 Correct 84 ms 2320 KB Output is correct
5 Correct 59 ms 1332 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1928 KB Output is correct
2 Correct 68 ms 1808 KB Output is correct
3 Correct 66 ms 1624 KB Output is correct
4 Correct 85 ms 2132 KB Output is correct
5 Correct 72 ms 1924 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2900 KB Output is correct
2 Correct 69 ms 1876 KB Output is correct
3 Correct 62 ms 1620 KB Output is correct
4 Correct 84 ms 2312 KB Output is correct
5 Correct 69 ms 1616 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 12760 KB Output is correct
2 Correct 357 ms 7940 KB Output is correct
3 Correct 340 ms 7568 KB Output is correct
4 Correct 434 ms 10008 KB Output is correct
5 Correct 367 ms 6992 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 8532 KB Output is correct
2 Correct 343 ms 7716 KB Output is correct
3 Correct 312 ms 7704 KB Output is correct
4 Correct 415 ms 9612 KB Output is correct
5 Correct 363 ms 8028 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 15420 KB Output is correct
2 Correct 428 ms 9556 KB Output is correct
3 Correct 413 ms 9044 KB Output is correct
4 Correct 545 ms 12428 KB Output is correct
5 Correct 428 ms 8328 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 10068 KB Output is correct
2 Correct 424 ms 9140 KB Output is correct
3 Correct 365 ms 8320 KB Output is correct
4 Correct 513 ms 12044 KB Output is correct
5 Correct 438 ms 9044 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 17948 KB Output is correct
2 Correct 511 ms 11092 KB Output is correct
3 Correct 478 ms 10392 KB Output is correct
4 Correct 596 ms 13852 KB Output is correct
5 Correct 498 ms 9296 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 11864 KB Output is correct
2 Correct 485 ms 10500 KB Output is correct
3 Correct 438 ms 10780 KB Output is correct
4 Correct 589 ms 13652 KB Output is correct
5 Correct 514 ms 10388 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 20732 KB Output is correct
2 Correct 622 ms 12680 KB Output is correct
3 Correct 550 ms 11788 KB Output is correct
4 Correct 682 ms 16144 KB Output is correct
5 Correct 612 ms 11544 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 13400 KB Output is correct
2 Correct 555 ms 11760 KB Output is correct
3 Correct 509 ms 11712 KB Output is correct
4 Correct 668 ms 15684 KB Output is correct
5 Correct 581 ms 11856 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 25360 KB Output is correct
2 Correct 698 ms 15824 KB Output is correct
3 Correct 712 ms 14932 KB Output is correct
4 Correct 848 ms 19600 KB Output is correct
5 Correct 733 ms 14108 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 16776 KB Output is correct
2 Correct 703 ms 14532 KB Output is correct
3 Correct 632 ms 15184 KB Output is correct
4 Correct 856 ms 19860 KB Output is correct
5 Correct 727 ms 15000 KB Output is correct