oj.uz

Submission #1102858

# Submission time Handle Problem Language Result Execution time Memory
1102858 2024-10-19T05:18:27 Z vjudge1 Mobile (BOI12_mobile) C++17
100 / 100
 653 ms 15176 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 {
	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; }
	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 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 = 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 504 KB Output is correct
3 Correct 1 ms 508 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 508 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 476 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 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 336 KB Output is correct
3 Correct 2 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 592 KB Output is correct
2 Correct 4 ms 496 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory 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 1 ms 336 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1016 KB Output is correct
2 Correct 37 ms 1020 KB Output is correct
3 Correct 29 ms 848 KB Output is correct
4 Correct 30 ms 848 KB Output is correct
5 Correct 6 ms 848 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 848 KB Output is correct
2 Correct 21 ms 848 KB Output is correct
3 Correct 32 ms 1016 KB Output is correct
4 Correct 32 ms 848 KB Output is correct
5 Correct 39 ms 1272 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1272 KB Output is correct
2 Correct 36 ms 1104 KB Output is correct
3 Correct 41 ms 1104 KB Output is correct
4 Correct 36 ms 1104 KB Output is correct
5 Correct 19 ms 1104 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1104 KB Output is correct
2 Correct 35 ms 1104 KB Output is correct
3 Correct 18 ms 1104 KB Output is correct
4 Correct 37 ms 1272 KB Output is correct
5 Correct 40 ms 1104 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1104 KB Output is correct
2 Correct 37 ms 1104 KB Output is correct
3 Correct 20 ms 1104 KB Output is correct
4 Correct 37 ms 1104 KB Output is correct
5 Correct 39 ms 1104 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 4176 KB Output is correct
2 Correct 78 ms 4176 KB Output is correct
3 Correct 80 ms 4176 KB Output is correct
4 Correct 187 ms 4188 KB Output is correct
5 Correct 171 ms 4176 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4176 KB Output is correct
2 Correct 311 ms 4176 KB Output is correct
3 Correct 111 ms 4176 KB Output is correct
4 Correct 186 ms 4176 KB Output is correct
5 Correct 185 ms 4176 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 4944 KB Output is correct
2 Correct 85 ms 4944 KB Output is correct
3 Correct 85 ms 4944 KB Output is correct
4 Correct 221 ms 4944 KB Output is correct
5 Correct 178 ms 4944 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4944 KB Output is correct
2 Correct 352 ms 4944 KB Output is correct
3 Correct 127 ms 4944 KB Output is correct
4 Correct 215 ms 4944 KB Output is correct
5 Correct 223 ms 4944 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 5712 KB Output is correct
2 Correct 100 ms 5712 KB Output is correct
3 Correct 97 ms 5712 KB Output is correct
4 Correct 253 ms 5712 KB Output is correct
5 Correct 175 ms 5712 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5712 KB Output is correct
2 Correct 398 ms 5880 KB Output is correct
3 Correct 138 ms 5712 KB Output is correct
4 Correct 242 ms 5712 KB Output is correct
5 Correct 258 ms 5712 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 6480 KB Output is correct
2 Correct 116 ms 6480 KB Output is correct
3 Correct 120 ms 6480 KB Output is correct
4 Correct 289 ms 6648 KB Output is correct
5 Correct 267 ms 6480 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 6480 KB Output is correct
2 Correct 442 ms 6480 KB Output is correct
3 Correct 147 ms 6480 KB Output is correct
4 Correct 313 ms 6480 KB Output is correct
5 Correct 293 ms 6480 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 8272 KB Output is correct
2 Correct 153 ms 8272 KB Output is correct
3 Correct 133 ms 8272 KB Output is correct
4 Correct 361 ms 8288 KB Output is correct
5 Correct 293 ms 15176 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 8272 KB Output is correct
2 Correct 584 ms 8272 KB Output is correct
3 Correct 206 ms 8272 KB Output is correct
4 Correct 413 ms 12924 KB Output is correct
5 Correct 380 ms 8272 KB Output is correct