Submission #1102860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102860	2024-10-19T05:21:16 Z	vjudge1	Mobile (BOI12_mobile)	C++17	20 / 100	481 ms	14588 KB

mobile

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
typedef long long ll;
typedef double ld;
const ld TOL = 1e-7;
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
inline bool eq(const ld& p, const ld& q) { return zero(p - q); }

int N, L;
struct Pos {
	int x, y;
	Pos(int X = 0, int Y = 0) : x(X), y(Y) {}
	bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = { 0, 0 };
typedef std::vector<Pos> Polygon;
bool eqx(const Pos& p, const Pos& q) { return p.x == q.x; }
std::pair<ld, ld> intersections(const Pos& p, const ld& d) {
	int y = std::abs(p.y);
	if (y && sign(y - d) > 0) return { -1, -1 };
	ld dx = sqrtl(d * d - y * y);
	ld x0 = std::max((ld)0, p.x - dx);
	ld x1 = std::min((ld)L, p.x + dx);
	return { x0, x1 };
}
bool F(const Polygon& B, const ld& d) {
	int sz = B.size();
	ld x = 0;
	for (int i = 0; i < sz; i++) {
		auto xx = intersections(B[i], d);
		ld x0 = xx.first, x1 = xx.second;
		if (sign(x - x0) >= 0) x = std::max(x, x1);
	}
	return eq(x, L);
}
ld bi_search(const Polygon& B) {
	int cnt = 40;
	ld s = 0, e = 2e9;
	while (cnt--) {
		ld m = (s + e) * .5;
		if (F(B, m)) e = m;
		else s = m;
	}
	return (s + e) * .5;
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(9);
	std::cin >> N >> L;
	Polygon B(N);
	for (Pos& p : B) std::cin >> p, p.y = std::abs(p.y);
	std::sort(B.begin(), B.end());
	B.erase(unique(B.begin(), B.end(), eqx), B.end());
	std::cout << bi_search(B) << "\n";
	return;
}
int main() { solve(); return 0; }//boj3346

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	336 KB	Output is correct
2	Correct	3 ms	336 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Incorrect	3 ms	504 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	1020 KB	Output is correct
2	Incorrect	33 ms	848 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	848 KB	Output is correct
2	Correct	22 ms	1616 KB	Output is correct
3	Correct	29 ms	848 KB	Output is correct
4	Correct	31 ms	848 KB	Output is correct
5	Incorrect	34 ms	1104 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	1356 KB	Output is correct
2	Incorrect	33 ms	848 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	1104 KB	Output is correct
2	Incorrect	32 ms	1104 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	1104 KB	Output is correct
2	Incorrect	33 ms	1104 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	233 ms	4176 KB	Output is correct
2	Correct	87 ms	8264 KB	Output is correct
3	Correct	72 ms	4176 KB	Output is correct
4	Incorrect	190 ms	8368 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	4176 KB	Output is correct
2	Correct	257 ms	4176 KB	Output is correct
3	Incorrect	91 ms	7240 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	278 ms	4944 KB	Output is correct
2	Correct	84 ms	4944 KB	Output is correct
3	Incorrect	100 ms	7620 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	4944 KB	Output is correct
2	Correct	308 ms	4944 KB	Output is correct
3	Incorrect	92 ms	4944 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	322 ms	5712 KB	Output is correct
2	Correct	101 ms	5712 KB	Output is correct
3	Correct	106 ms	11080 KB	Output is correct
4	Incorrect	250 ms	5712 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	5712 KB	Output is correct
2	Correct	351 ms	5712 KB	Output is correct
3	Incorrect	119 ms	5712 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	357 ms	6480 KB	Output is correct
2	Correct	106 ms	6480 KB	Output is correct
3	Correct	111 ms	11376 KB	Output is correct
4	Incorrect	282 ms	14412 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	6480 KB	Output is correct
2	Correct	377 ms	6480 KB	Output is correct
3	Incorrect	131 ms	6480 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	448 ms	8272 KB	Output is correct
2	Correct	144 ms	8272 KB	Output is correct
3	Incorrect	135 ms	8272 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	8272 KB	Output is correct
2	Correct	481 ms	9400 KB	Output is correct
3	Incorrect	192 ms	14588 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Submission #1102860

Compilation message