oj.uz

Submission #952751

# Submission time Handle Problem Language Result Execution time Memory
952751 2024-03-24T16:51:49 Z artixkrishna Mobile (BOI12_mobile) C++14
100 / 100
 865 ms 25308 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:64:15: warning: narrowing conversion of 'l' from 'int' to 'double' [-Wnarrowing]
   64 |   Point right{l, 0};
      |               ^

Subtask #1
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
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 604 KB Output is correct
4 Correct 4 ms 348 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1112 KB Output is correct
2 Correct 53 ms 1368 KB Output is correct
3 Correct 33 ms 864 KB Output is correct
4 Correct 58 ms 1552 KB Output is correct
5 Correct 28 ms 604 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1108 KB Output is correct
2 Correct 46 ms 1104 KB Output is correct
3 Correct 60 ms 1440 KB Output is correct
4 Correct 60 ms 1616 KB Output is correct
5 Correct 71 ms 1872 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2384 KB Output is correct
2 Correct 57 ms 1360 KB Output is correct
3 Correct 54 ms 2552 KB Output is correct
4 Correct 87 ms 2132 KB Output is correct
5 Correct 59 ms 1300 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1804 KB Output is correct
2 Correct 69 ms 1924 KB Output is correct
3 Correct 60 ms 1444 KB Output is correct
4 Correct 89 ms 2384 KB Output is correct
5 Correct 71 ms 1672 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2908 KB Output is correct
2 Correct 68 ms 1616 KB Output is correct
3 Correct 59 ms 1616 KB Output is correct
4 Correct 84 ms 2132 KB Output is correct
5 Correct 68 ms 1544 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 12912 KB Output is correct
2 Correct 354 ms 8080 KB Output is correct
3 Correct 343 ms 7432 KB Output is correct
4 Correct 443 ms 9732 KB Output is correct
5 Correct 354 ms 7240 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 8588 KB Output is correct
2 Correct 345 ms 7760 KB Output is correct
3 Correct 302 ms 7708 KB Output is correct
4 Correct 432 ms 9872 KB Output is correct
5 Correct 362 ms 7716 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 15576 KB Output is correct
2 Correct 428 ms 9676 KB Output is correct
3 Correct 418 ms 8856 KB Output is correct
4 Correct 541 ms 12112 KB Output is correct
5 Correct 416 ms 8272 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 10260 KB Output is correct
2 Correct 416 ms 9088 KB Output is correct
3 Correct 370 ms 8320 KB Output is correct
4 Correct 570 ms 11924 KB Output is correct
5 Correct 433 ms 9044 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 17900 KB Output is correct
2 Correct 517 ms 11152 KB Output is correct
3 Correct 484 ms 10580 KB Output is correct
4 Correct 633 ms 13912 KB Output is correct
5 Correct 475 ms 9304 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 11852 KB Output is correct
2 Correct 527 ms 10528 KB Output is correct
3 Correct 464 ms 10808 KB Output is correct
4 Correct 586 ms 13592 KB Output is correct
5 Correct 514 ms 10380 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 20448 KB Output is correct
2 Correct 557 ms 12628 KB Output is correct
3 Correct 631 ms 11860 KB Output is correct
4 Correct 690 ms 16016 KB Output is correct
5 Correct 567 ms 11416 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 13444 KB Output is correct
2 Correct 553 ms 11968 KB Output is correct
3 Correct 497 ms 11844 KB Output is correct
4 Correct 686 ms 15876 KB Output is correct
5 Correct 579 ms 11856 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 25308 KB Output is correct
2 Correct 704 ms 15748 KB Output is correct
3 Correct 707 ms 14932 KB Output is correct
4 Correct 859 ms 19604 KB Output is correct
5 Correct 712 ms 13980 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 17172 KB Output is correct
2 Correct 688 ms 14672 KB Output is correct
3 Correct 637 ms 15048 KB Output is correct
4 Correct 865 ms 19920 KB Output is correct
5 Correct 738 ms 15380 KB Output is correct