oj.uz

답안 #1102862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102862 2024-10-19T05:22:57 Z vjudge1 Mobile (BOI12_mobile) C++17
100 / 100
 579 ms 14152 KB 
#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) {
	ll y = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 504 KB Output is correct

Subtask #3
4.0 / 4.0

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

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

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 848 KB Output is correct
2 Correct 38 ms 848 KB Output is correct
3 Correct 30 ms 848 KB Output is correct
4 Correct 33 ms 1616 KB Output is correct
5 Correct 8 ms 1104 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 848 KB Output is correct
2 Correct 21 ms 848 KB Output is correct
3 Correct 31 ms 848 KB Output is correct
4 Correct 32 ms 848 KB Output is correct
5 Correct 33 ms 1104 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 1272 KB Output is correct
2 Correct 36 ms 848 KB Output is correct
3 Correct 40 ms 1104 KB Output is correct
4 Correct 37 ms 1104 KB Output is correct
5 Correct 18 ms 1616 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 1104 KB Output is correct
2 Correct 33 ms 1104 KB Output is correct
3 Correct 18 ms 1276 KB Output is correct
4 Correct 36 ms 1104 KB Output is correct
5 Correct 37 ms 1104 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 1104 KB Output is correct
2 Correct 33 ms 1104 KB Output is correct
3 Correct 18 ms 1104 KB Output is correct
4 Correct 39 ms 1104 KB Output is correct
5 Correct 37 ms 1516 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 4176 KB Output is correct
2 Correct 74 ms 4176 KB Output is correct
3 Correct 68 ms 4176 KB Output is correct
4 Correct 181 ms 4176 KB Output is correct
5 Correct 157 ms 4176 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 4176 KB Output is correct
2 Correct 275 ms 4176 KB Output is correct
3 Correct 97 ms 4176 KB Output is correct
4 Correct 186 ms 4176 KB Output is correct
5 Correct 186 ms 4176 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 4944 KB Output is correct
2 Correct 85 ms 4944 KB Output is correct
3 Correct 84 ms 4944 KB Output is correct
4 Correct 213 ms 8376 KB Output is correct
5 Correct 178 ms 5108 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 5112 KB Output is correct
2 Correct 332 ms 4944 KB Output is correct
3 Correct 104 ms 4944 KB Output is correct
4 Correct 214 ms 5112 KB Output is correct
5 Correct 214 ms 4944 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 5712 KB Output is correct
2 Correct 100 ms 5712 KB Output is correct
3 Correct 94 ms 5712 KB Output is correct
4 Correct 260 ms 5712 KB Output is correct
5 Correct 191 ms 8304 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 5712 KB Output is correct
2 Correct 379 ms 5712 KB Output is correct
3 Correct 142 ms 5712 KB Output is correct
4 Correct 245 ms 5712 KB Output is correct
5 Correct 252 ms 5712 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 470 ms 6480 KB Output is correct
2 Correct 110 ms 6480 KB Output is correct
3 Correct 108 ms 6480 KB Output is correct
4 Correct 301 ms 6480 KB Output is correct
5 Correct 252 ms 9572 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 6480 KB Output is correct
2 Correct 434 ms 6480 KB Output is correct
3 Correct 148 ms 6480 KB Output is correct
4 Correct 316 ms 12608 KB Output is correct
5 Correct 297 ms 6480 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 8272 KB Output is correct
2 Correct 134 ms 8272 KB Output is correct
3 Correct 130 ms 8272 KB Output is correct
4 Correct 363 ms 8284 KB Output is correct
5 Correct 269 ms 8272 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 8284 KB Output is correct
2 Correct 541 ms 8272 KB Output is correct
3 Correct 186 ms 8272 KB Output is correct
4 Correct 367 ms 8272 KB Output is correct
5 Correct 365 ms 14152 KB Output is correct