oj.uz

답안 #1102855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102855 2024-10-19T05:15:48 Z vjudge1 Mobile (BOI12_mobile) C++17
100 / 100
 638 ms 16120 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ll INF = 1e17;
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;
ll L;
struct Pos {
	ll x, y;
	Pos(ll X = 0, ll Y = 0) : x(X), y(Y) {}
	bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
	bool operator != (const Pos& p) const { return x != p.x || y != p.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 cmpx(const Pos& p, const Pos& q) { return p.x == q.x; }
std::pair<ld, ld> intersections(const Pos& p, const ld& d) {
	ll 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(), cmpx), 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 456 KB Output is correct
4 Correct 1 ms 356 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 3 ms 348 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 344 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 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 43 ms 1628 KB Output is correct
2 Correct 40 ms 1628 KB Output is correct
3 Correct 31 ms 1116 KB Output is correct
4 Correct 31 ms 1628 KB Output is correct
5 Correct 7 ms 1116 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1628 KB Output is correct
2 Correct 23 ms 1372 KB Output is correct
3 Correct 33 ms 1628 KB Output is correct
4 Correct 34 ms 1628 KB Output is correct
5 Correct 35 ms 1628 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 1628 KB Output is correct
2 Correct 38 ms 1628 KB Output is correct
3 Correct 43 ms 1628 KB Output is correct
4 Correct 37 ms 1872 KB Output is correct
5 Correct 18 ms 1784 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1872 KB Output is correct
2 Correct 36 ms 2044 KB Output is correct
3 Correct 19 ms 1872 KB Output is correct
4 Correct 37 ms 1872 KB Output is correct
5 Correct 38 ms 1872 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 1872 KB Output is correct
2 Correct 37 ms 1872 KB Output is correct
3 Correct 19 ms 1872 KB Output is correct
4 Correct 38 ms 1872 KB Output is correct
5 Correct 39 ms 1872 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 8272 KB Output is correct
2 Correct 79 ms 8272 KB Output is correct
3 Correct 72 ms 8272 KB Output is correct
4 Correct 181 ms 8272 KB Output is correct
5 Correct 168 ms 8272 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 8272 KB Output is correct
2 Correct 305 ms 8272 KB Output is correct
3 Correct 109 ms 8272 KB Output is correct
4 Correct 176 ms 8272 KB Output is correct
5 Correct 195 ms 8272 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 9808 KB Output is correct
2 Correct 80 ms 9808 KB Output is correct
3 Correct 78 ms 9808 KB Output is correct
4 Correct 209 ms 9808 KB Output is correct
5 Correct 172 ms 10048 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 9808 KB Output is correct
2 Correct 337 ms 9808 KB Output is correct
3 Correct 95 ms 9808 KB Output is correct
4 Correct 209 ms 9808 KB Output is correct
5 Correct 241 ms 9808 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 11344 KB Output is correct
2 Correct 100 ms 11344 KB Output is correct
3 Correct 98 ms 11344 KB Output is correct
4 Correct 259 ms 11344 KB Output is correct
5 Correct 199 ms 11344 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 11344 KB Output is correct
2 Correct 415 ms 11344 KB Output is correct
3 Correct 136 ms 11512 KB Output is correct
4 Correct 258 ms 11344 KB Output is correct
5 Correct 280 ms 11344 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 487 ms 12880 KB Output is correct
2 Correct 125 ms 12880 KB Output is correct
3 Correct 105 ms 12880 KB Output is correct
4 Correct 278 ms 12880 KB Output is correct
5 Correct 255 ms 13048 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 12880 KB Output is correct
2 Correct 458 ms 12880 KB Output is correct
3 Correct 158 ms 12880 KB Output is correct
4 Correct 302 ms 12880 KB Output is correct
5 Correct 286 ms 12880 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 638 ms 16120 KB Output is correct
2 Correct 135 ms 15952 KB Output is correct
3 Correct 150 ms 15952 KB Output is correct
4 Correct 339 ms 15952 KB Output is correct
5 Correct 263 ms 15952 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 15952 KB Output is correct
2 Correct 532 ms 15952 KB Output is correct
3 Correct 179 ms 15952 KB Output is correct
4 Correct 338 ms 15952 KB Output is correct
5 Correct 362 ms 15952 KB Output is correct