Submission #927926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927926	2024-02-15T14:07:24 Z	TAhmed33	Mobile (BOI12_mobile)	C++	100 / 100	209 ms	41656 KB

mobile

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
int n, l;
ld inter (pair <int, int> &a, pair <int, int> &b) {
	return 1.0 * (a.second - b.second) / (b.first - a.first);
}
const ld eps = 1e-9;
ld get (pair <int, int> &a, ld b, ld c) {
	return max(b * b + a.first * b + a.second, c * c + a.first * c + a.second);
}
vector <pair <int, int>> dd;
deque <pair <int, int>> hull;
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> l;
	cout << fixed << setprecision(9);

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		int m = -2 * a;
		int c = a * a + b * b;
		dd.push_back({m, c});
	}
	sort(dd.begin(), dd.end());
	int prev = -1e9 + 7;
	for (auto i : dd) {
		pair <int, int> x = i;
		if (x.first == prev) continue;
		prev = x.first;
		if (hull.size() < 2) {
			hull.push_front(x);
			continue;
		}
		while (hull.size() >= 2) {
			ld a = inter(hull[0], hull[1]), b = inter(x, hull[0]);
			if (a + eps < b) {
				hull.pop_front();
			} else {
				break;
			}
		}
		hull.push_front(x);
	}
	while (hull.size() >= 2) {
		if (inter(hull[0], hull[1]) < eps) hull.pop_front();
		else break;
	}
	while (hull.size() >= 2) {
		if (inter(hull.back(), hull[hull.size() - 2]) > l + eps) hull.pop_back();
		else break;
	}
	ld ans = 0;
	if (hull.size() == 1) {
		ans = get(hull[0], 0, l);
		cout << sqrt(ans) << '\n';
		return 0;
	} 
	ans = max(get(hull[0], 0, inter(hull[0], hull[1])), get(hull.back(), inter(hull.back(), hull[hull.size() - 2]), l));
	for (int i = 1; i < (int)hull.size() - 1; i++) {
		ans = max(ans, get(hull[i], inter(hull[i], hull[i - 1]), inter(hull[i], hull[i + 1])));
	}
	cout << sqrt(ans) << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
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	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	568 KB	Output is correct
2	Correct	2 ms	860 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	600 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	3312 KB	Output is correct
2	Correct	13 ms	3620 KB	Output is correct
3	Correct	8 ms	2012 KB	Output is correct
4	Correct	15 ms	3800 KB	Output is correct
5	Correct	8 ms	2008 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3284 KB	Output is correct
2	Correct	13 ms	3288 KB	Output is correct
3	Correct	15 ms	3544 KB	Output is correct
4	Correct	15 ms	3796 KB	Output is correct
5	Correct	17 ms	3800 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3792 KB	Output is correct
2	Correct	14 ms	3800 KB	Output is correct
3	Correct	14 ms	3796 KB	Output is correct
4	Correct	21 ms	4064 KB	Output is correct
5	Correct	15 ms	3288 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3800 KB	Output is correct
2	Correct	16 ms	3544 KB	Output is correct
3	Correct	14 ms	3288 KB	Output is correct
4	Correct	25 ms	4052 KB	Output is correct
5	Correct	18 ms	3540 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	4564 KB	Output is correct
2	Correct	16 ms	3800 KB	Output is correct
3	Correct	14 ms	3288 KB	Output is correct
4	Correct	21 ms	4056 KB	Output is correct
5	Correct	18 ms	3656 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	20576 KB	Output is correct
2	Correct	91 ms	16576 KB	Output is correct
3	Correct	82 ms	15452 KB	Output is correct
4	Correct	102 ms	17788 KB	Output is correct
5	Correct	88 ms	15032 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	16568 KB	Output is correct
2	Correct	81 ms	15660 KB	Output is correct
3	Correct	75 ms	15540 KB	Output is correct
4	Correct	98 ms	17592 KB	Output is correct
5	Correct	88 ms	15508 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	25568 KB	Output is correct
2	Correct	100 ms	25340 KB	Output is correct
3	Correct	100 ms	26384 KB	Output is correct
4	Correct	125 ms	28332 KB	Output is correct
5	Correct	106 ms	24756 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	26180 KB	Output is correct
2	Correct	100 ms	24248 KB	Output is correct
3	Correct	86 ms	24816 KB	Output is correct
4	Correct	125 ms	27320 KB	Output is correct
5	Correct	107 ms	25016 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	29100 KB	Output is correct
2	Correct	121 ms	26824 KB	Output is correct
3	Correct	118 ms	25272 KB	Output is correct
4	Correct	143 ms	27828 KB	Output is correct
5	Correct	117 ms	25244 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	26552 KB	Output is correct
2	Correct	121 ms	23992 KB	Output is correct
3	Correct	100 ms	25012 KB	Output is correct
4	Correct	147 ms	28184 KB	Output is correct
5	Correct	126 ms	25584 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	33452 KB	Output is correct
2	Correct	140 ms	27312 KB	Output is correct
3	Correct	136 ms	24992 KB	Output is correct
4	Correct	164 ms	28564 KB	Output is correct
5	Correct	142 ms	25780 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	26276 KB	Output is correct
2	Correct	133 ms	25260 KB	Output is correct
3	Correct	113 ms	25004 KB	Output is correct
4	Correct	170 ms	28868 KB	Output is correct
5	Correct	141 ms	25184 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	41656 KB	Output is correct
2	Correct	167 ms	31672 KB	Output is correct
3	Correct	166 ms	30636 KB	Output is correct
4	Correct	201 ms	35248 KB	Output is correct
5	Correct	182 ms	29608 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	32796 KB	Output is correct
2	Correct	170 ms	30312 KB	Output is correct
3	Correct	145 ms	30768 KB	Output is correct
4	Correct	209 ms	35752 KB	Output is correct
5	Correct	181 ms	30984 KB	Output is correct

Submission #927926

Compilation message