답안 #935546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935546	2024-02-29T09:00:58 Z	cryan	Mobile (BOI12_mobile)	C++17	100 / 100	443 ms	33184 KB

mobile

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#else
#define endl '\n'
#endif

#define double long double
struct Point {
	double x, y;
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, l;
	cin >> n >> l;

	function<double(Point, Point)> max_point = [&](Point a, Point b) {
		// return (((b.x) * (b.x)) + ((b.y) * (b.y)) - ((a.x) * (a.x)) - ((a.y) * (a.y))) / (2 * (b.x - a.x));
		return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x);
	};

	function<double(Point, Point)> dist = [&](Point a, Point b) {
		return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
	};

	deque<Point> stck;
	for (int i = 0; i < n; i++) {
		Point cur;
		cin >> cur.x >> cur.y;
		cur.y = abs(cur.y);

		// take the one with the lowest y coord
		if (sz(stck) && 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 (sz(stck) > 1 && max_point(stck[sz(stck) - 2], stck.back()) > max_point(stck.back(), cur)) {
			stck.pop_back();
		}

		stck.push_back(cur);
	}

	while (sz(stck) > 1 && max_point(stck[0], stck[1]) < 0)
		stck.pop_front();
	while (sz(stck) > 1 && max_point(stck[sz(stck) - 2], stck.back()) > l)
		stck.pop_back();

	double ans = 0;
	for (int x = 0; x < sz(stck); x++) {
		Point left = {(x ? max_point(stck[x], stck[x - 1]) : 0), 0};
		Point right = {(x < sz(stck) - 1 ? max_point(stck[x], stck[x + 1]) : l), 0};
		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;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	456 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	1 ms	536 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	600 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	3 ms	344 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	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	3 ms	348 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	604 KB	Output is correct
2	Correct	29 ms	344 KB	Output is correct
3	Correct	19 ms	472 KB	Output is correct
4	Correct	31 ms	476 KB	Output is correct
5	Correct	15 ms	836 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	344 KB	Output is correct
2	Correct	32 ms	1052 KB	Output is correct
3	Correct	36 ms	1208 KB	Output is correct
4	Correct	36 ms	1304 KB	Output is correct
5	Correct	37 ms	1360 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	3164 KB	Output is correct
2	Correct	38 ms	1196 KB	Output is correct
3	Correct	31 ms	3672 KB	Output is correct
4	Correct	45 ms	2236 KB	Output is correct
5	Correct	30 ms	1360 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	348 KB	Output is correct
2	Correct	35 ms	348 KB	Output is correct
3	Correct	30 ms	848 KB	Output is correct
4	Correct	48 ms	708 KB	Output is correct
5	Correct	42 ms	476 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	2396 KB	Output is correct
2	Correct	35 ms	348 KB	Output is correct
3	Correct	37 ms	860 KB	Output is correct
4	Correct	43 ms	472 KB	Output is correct
5	Correct	38 ms	468 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	205 ms	16996 KB	Output is correct
2	Correct	166 ms	4744 KB	Output is correct
3	Correct	158 ms	4176 KB	Output is correct
4	Correct	220 ms	5352 KB	Output is correct
5	Correct	198 ms	4052 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	170 ms	460 KB	Output is correct
2	Correct	203 ms	5756 KB	Output is correct
3	Correct	155 ms	6480 KB	Output is correct
4	Correct	225 ms	5340 KB	Output is correct
5	Correct	219 ms	4208 KB	Output is correct

Subtask #14
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	20136 KB	Output is correct
2	Correct	196 ms	5456 KB	Output is correct
3	Correct	190 ms	9008 KB	Output is correct
4	Correct	272 ms	12204 KB	Output is correct
5	Correct	261 ms	8240 KB	Output is correct

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	194 ms	448 KB	Output is correct
2	Correct	227 ms	6228 KB	Output is correct
3	Correct	177 ms	6052 KB	Output is correct
4	Correct	271 ms	12116 KB	Output is correct
5	Correct	238 ms	9040 KB	Output is correct

Subtask #16
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	270 ms	23248 KB	Output is correct
2	Correct	233 ms	6224 KB	Output is correct
3	Correct	221 ms	10576 KB	Output is correct
4	Correct	317 ms	14008 KB	Output is correct
5	Correct	265 ms	9300 KB	Output is correct

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	228 ms	696 KB	Output is correct
2	Correct	271 ms	7152 KB	Output is correct
3	Correct	217 ms	8784 KB	Output is correct
4	Correct	351 ms	13636 KB	Output is correct
5	Correct	282 ms	10440 KB	Output is correct

Subtask #18
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	318 ms	26688 KB	Output is correct
2	Correct	259 ms	7012 KB	Output is correct
3	Correct	258 ms	12076 KB	Output is correct
4	Correct	355 ms	16048 KB	Output is correct
5	Correct	330 ms	11732 KB	Output is correct

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	269 ms	600 KB	Output is correct
2	Correct	304 ms	7908 KB	Output is correct
3	Correct	244 ms	9556 KB	Output is correct
4	Correct	355 ms	15828 KB	Output is correct
5	Correct	317 ms	12136 KB	Output is correct

Subtask #20
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	378 ms	33184 KB	Output is correct
2	Correct	320 ms	8492 KB	Output is correct
3	Correct	316 ms	14904 KB	Output is correct
4	Correct	437 ms	19672 KB	Output is correct
5	Correct	392 ms	14272 KB	Output is correct

Subtask #21
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	322 ms	344 KB	Output is correct
2	Correct	381 ms	9456 KB	Output is correct
3	Correct	317 ms	11856 KB	Output is correct
4	Correct	443 ms	10688 KB	Output is correct
5	Correct	409 ms	8408 KB	Output is correct

답안 #935546

Compilation message