oj.uz

답안 #935528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935528 2024-02-29T08:48:45 Z cryan Mobile (BOI12_mobile) C++17
28 / 100
 447 ms 35248 KB 
// 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));
	};

	vector<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);
	}

	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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

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

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

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

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 792 KB Output is correct
2 Incorrect 31 ms 500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 476 KB Output is correct
2 Correct 33 ms 348 KB Output is correct
3 Correct 31 ms 348 KB Output is correct
4 Correct 32 ms 496 KB Output is correct
5 Correct 38 ms 404 KB Output is correct

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 5076 KB Output is correct
2 Incorrect 30 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 2512 KB Output is correct
2 Incorrect 36 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 18360 KB Output is correct
2 Correct 180 ms 344 KB Output is correct
3 Correct 175 ms 348 KB Output is correct
4 Correct 219 ms 344 KB Output is correct
5 Correct 197 ms 856 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 348 KB Output is correct
2 Correct 189 ms 2512 KB Output is correct
3 Correct 185 ms 6316 KB Output is correct
4 Correct 217 ms 9812 KB Output is correct
5 Correct 213 ms 7760 KB Output is correct

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 33960 KB Output is correct
2 Incorrect 214 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 704 KB Output is correct
2 Correct 231 ms 2644 KB Output is correct
3 Incorrect 194 ms 6472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 34796 KB Output is correct
2 Incorrect 246 ms 444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 348 KB Output is correct
2 Correct 263 ms 2508 KB Output is correct
3 Incorrect 230 ms 5576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 35248 KB Output is correct
2 Incorrect 271 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 596 KB Output is correct
2 Correct 302 ms 2512 KB Output is correct
3 Incorrect 264 ms 5696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 33448 KB Output is correct
2 Incorrect 355 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 401 ms 348 KB Output is correct
2 Correct 377 ms 6472 KB Output is correct
3 Correct 331 ms 9664 KB Output is correct
4 Correct 447 ms 19780 KB Output is correct
5 Correct 403 ms 15184 KB Output is correct