Submission #974145

# Submission time Handle Problem Language Result Execution time Memory
974145 2024-05-02T23:14:26 Z AksLolCoding Mobile (BOI12_mobile) C++17
90 / 100
1000 ms 31772 KB
#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using ld2 = array<ld, 2>;

const ld diff = 5e-4;
int n;
ld h;
vector<ld2> pts;

ld2 range(ld dist, ld2& pt) {
	ld dx = sqrt(dist*dist - pt[1]*pt[1]);
	return {pt[0] - dx, pt[0] + dx};
}

bool check(ld dist) {
	ld left = 0;
	for (ld2& pt: pts) {
		ld2 r = range(dist, pt);
		if (r[0] <= left) left = max(left, r[1]);
	}
	return (left >= h);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> h;
	pts.resize(n);
	for (auto& i: pts) cin >> i[0] >> i[1];

	// solve
	ld l = 0, r = 1.5e9, m;
	while (r - l > diff) {
		m = (r + l) / 2;
		if (check(m)) r = m;
		else l = m;
	}
	printf("%.4Lf\n", m);
}
# 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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
# 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 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 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
# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 56 ms 2652 KB Output is correct
2 Correct 39 ms 2652 KB Output is correct
3 Correct 33 ms 2140 KB Output is correct
4 Correct 78 ms 2896 KB Output is correct
5 Correct 36 ms 1884 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 60 ms 2904 KB Output is correct
2 Correct 58 ms 2652 KB Output is correct
3 Correct 69 ms 2908 KB Output is correct
4 Correct 74 ms 2928 KB Output is correct
5 Correct 88 ms 3164 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 3164 KB Output is correct
2 Correct 43 ms 2908 KB Output is correct
3 Correct 60 ms 3104 KB Output is correct
4 Correct 103 ms 3420 KB Output is correct
5 Correct 76 ms 3244 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 52 ms 3416 KB Output is correct
2 Correct 54 ms 3588 KB Output is correct
3 Correct 58 ms 3420 KB Output is correct
4 Correct 105 ms 3420 KB Output is correct
5 Correct 88 ms 3588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 54 ms 3416 KB Output is correct
2 Correct 59 ms 3416 KB Output is correct
3 Correct 59 ms 3416 KB Output is correct
4 Correct 103 ms 3420 KB Output is correct
5 Correct 94 ms 3416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 252 ms 15964 KB Output is correct
2 Correct 276 ms 15964 KB Output is correct
3 Correct 262 ms 15960 KB Output is correct
4 Correct 517 ms 16112 KB Output is correct
5 Correct 437 ms 15964 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 286 ms 16208 KB Output is correct
2 Correct 398 ms 16112 KB Output is correct
3 Correct 298 ms 15960 KB Output is correct
4 Correct 506 ms 15964 KB Output is correct
5 Correct 458 ms 16116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 317 ms 19280 KB Output is correct
2 Correct 322 ms 19240 KB Output is correct
3 Correct 323 ms 19440 KB Output is correct
4 Correct 624 ms 19032 KB Output is correct
5 Correct 534 ms 19244 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 358 ms 19032 KB Output is correct
2 Correct 483 ms 19036 KB Output is correct
3 Correct 380 ms 19240 KB Output is correct
4 Correct 627 ms 19240 KB Output is correct
5 Correct 543 ms 19032 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 359 ms 22380 KB Output is correct
2 Correct 382 ms 22368 KB Output is correct
3 Correct 381 ms 22364 KB Output is correct
4 Correct 722 ms 22372 KB Output is correct
5 Correct 628 ms 22372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 388 ms 22360 KB Output is correct
2 Correct 593 ms 22376 KB Output is correct
3 Correct 421 ms 22376 KB Output is correct
4 Correct 719 ms 22608 KB Output is correct
5 Correct 637 ms 22376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 393 ms 25436 KB Output is correct
2 Correct 432 ms 25512 KB Output is correct
3 Correct 474 ms 25432 KB Output is correct
4 Correct 825 ms 25680 KB Output is correct
5 Correct 716 ms 25504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 431 ms 25756 KB Output is correct
2 Correct 691 ms 25500 KB Output is correct
3 Correct 516 ms 25680 KB Output is correct
4 Correct 824 ms 25504 KB Output is correct
5 Correct 723 ms 25512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 519 ms 31768 KB Output is correct
2 Correct 550 ms 31768 KB Output is correct
3 Correct 572 ms 31764 KB Output is correct
4 Execution timed out 1029 ms 31768 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 545 ms 31764 KB Output is correct
2 Correct 788 ms 31772 KB Output is correct
3 Correct 598 ms 31768 KB Output is correct
4 Execution timed out 1038 ms 31764 KB Time limit exceeded
5 Halted 0 ms 0 KB -