oj.uz

Submission #1102853

# Submission time Handle Problem Language Result Execution time Memory
1102853 2024-10-19T05:12:31 Z vjudge1 Mobile (BOI12_mobile) C++17
90 / 100
 1000 ms 28196 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;
typedef std::pair<int, int> pi;
typedef std::vector<int> Vint;
typedef std::vector<ld> Vld;
const ll INF = 1e17;
const int LEN = 1e5 + 1;
const ld TOL = 1e-7;
const ll MOD = 1'000'000'007;
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); }
inline ll sq(ll x) { return (ll)x * x; }

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; }
	bool operator <= (const Pos& p) const { return x == p.x ? y <= p.y : x <= p.x; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	Pos operator * (const ll& n) const { return { x * n, y * n }; }
	Pos operator / (const ll& n) const { return { x / n, y / n }; }
	ll operator * (const Pos& p) const { return x * p.x + y * p.y; }
	ll operator / (const Pos& p) const { return x * p.y - y * p.x; }
	Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
	Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
	Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
	Pos& operator *= (const ll& scale) { x *= scale; y *= scale; return *this; }
	Pos& operator /= (const ll& scale) { x /= scale; y /= scale; return *this; }
	Pos operator - () const { return { -x, -y }; }
	Pos operator ~ () const { return { -y, x }; }
	Pos operator ! () const { return { y, x }; }
	ld xy() const { return x * y; }
	ll Euc() const { return x * x + y * y; }
	ll Man() const { return std::abs(x) + std::abs(y); }
	ld mag() const { return hypot(x, y); }
	ld rad() const { return atan2(y, x); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	int quad() const { return y > 0 || y == 0 && x >= 0; }
	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
	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; }
struct E {
	ld x;
	int f;
	E(ld x_ = 0, int f_ = 0) : x(x_), f(f_) {}
	bool operator < (const E& e) const {
		return eq(x, e.x) ? f < e.f : sign(x - e.x) < 0;
	}
};
bool sweep(const Polygon& B, const ld& d) {
	std::vector<E> tmp;
	Pos s = Pos(0, 0), e = Pos(L, 0);
	Pos vec = e - s;
	tmp.push_back(E(0, 0));
	tmp.push_back(E(1, 0));
	for (int i = 0; i < N; i++) {
		Pos OM = s - B[i];
		ld a = vec * vec;
		ld b = 2 * (vec * OM);
		ld c = OM * OM - d * d;
		ld J = b * b - 4 * a * c;
		if (J < TOL) continue;
		else {
			ld ret1 = (-b + sqrt(J)) / (2 * a);
			ld ret2 = (-b - sqrt(J)) / (2 * a);
			ret1 = std::min(ret1, (ld)1.);
			ret2 = std::min(ret2, (ld)1.);
			if (ret2 < ret1) std::swap(ret1, ret2);
			tmp.push_back(E(ret1, -1));
			tmp.push_back(E(ret2, 1));
		}
	}
	int toggle = 0;
	bool f = 0;
	std::sort(tmp.begin(), tmp.end());
	for (const E& d : tmp) {
		toggle -= d.f;
		if (!d.f) f = !f;
		if (f && toggle <= 0) return 1;
	}
	return 0;
}
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;
		//std::cout << "x0:: " << x0 << " x1:: " << x1 << "\n";
		if (sign(x - x0) >= 0) x = std::max(x, x1);
	}
	return eq(x, L);
}
ld bi_search(const Polygon& B) {
	int cnt = 50;
	ld s = 0, e = 2e9;
	while (cnt--) {
		//std::cout << cnt << "\n";
		ld m = (s + e) * .5;
		//if (sweep(B, m)) s = m;
		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 << B.size() << " fuck::\n";
	std::cout << bi_search(B) << "\n";
	return;
}
int main() { solve(); return 0; }//boj3346

//bool F(const Polygon& B, const ld& d) {
//	std::vector<E> tmp;
//	Pos s = Pos(0, 0), e = Pos(L, 0);
//	Pos vec = e - s;
//	tmp.push_back(E(0, 0));
//	tmp.push_back(E(L, 0));
//	for (int i = 0; i < N; i++) {
//		ll y = std::abs(B[i].y);
//		ld dx = sqrt(d * d - y * y);
//		ld x0 = std::max((ld)0, B[i].x - dx);
//		ld x1 = std::min((ld)L, B[i].x + dx);
//		tmp.push_back(E(x0, -1));
//		tmp.push_back(E(x1, 1));
//	}
//	int t = 0;
//	bool f = 0;
//	std::sort(tmp.begin(), tmp.end());
//	for (const E& d : tmp) {
//		t -= d.f;
//		if (!d.f) f = !f;
//		if (f && t <= 0) return 1;
//	}
//	return 0;
//}

Compilation message

mobile.cpp: In member function 'int Pos::quad() const':
mobile.cpp:52:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |  int quad() const { return y > 0 || y == 0 && x >= 0; }
      |                                     ~~~~~~~^~~~~~~~~

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 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 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 2 ms 508 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 3 ms 352 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 348 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 7 ms 352 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 624 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 7 ms 608 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 6 ms 608 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1628 KB Output is correct
2 Correct 68 ms 1632 KB Output is correct
3 Correct 76 ms 1884 KB Output is correct
4 Correct 77 ms 2792 KB Output is correct
5 Correct 8 ms 1628 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1628 KB Output is correct
2 Correct 44 ms 2144 KB Output is correct
3 Correct 67 ms 1628 KB Output is correct
4 Correct 73 ms 2908 KB Output is correct
5 Correct 92 ms 2640 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1616 KB Output is correct
2 Correct 69 ms 2896 KB Output is correct
3 Correct 83 ms 2640 KB Output is correct
4 Correct 92 ms 1872 KB Output is correct
5 Correct 37 ms 2384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1872 KB Output is correct
2 Correct 57 ms 1872 KB Output is correct
3 Correct 32 ms 2896 KB Output is correct
4 Correct 93 ms 2040 KB Output is correct
5 Correct 99 ms 1872 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1872 KB Output is correct
2 Correct 61 ms 2904 KB Output is correct
3 Correct 35 ms 2648 KB Output is correct
4 Correct 99 ms 3280 KB Output is correct
5 Correct 88 ms 2640 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 8440 KB Output is correct
2 Correct 90 ms 15792 KB Output is correct
3 Correct 79 ms 12112 KB Output is correct
4 Correct 471 ms 15808 KB Output is correct
5 Correct 348 ms 8272 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 8272 KB Output is correct
2 Correct 661 ms 8272 KB Output is correct
3 Correct 160 ms 13900 KB Output is correct
4 Correct 433 ms 8440 KB Output is correct
5 Correct 431 ms 8272 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 9808 KB Output is correct
2 Correct 84 ms 9808 KB Output is correct
3 Correct 84 ms 14352 KB Output is correct
4 Correct 543 ms 15952 KB Output is correct
5 Correct 380 ms 14152 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9808 KB Output is correct
2 Correct 853 ms 9808 KB Output is correct
3 Correct 131 ms 9808 KB Output is correct
4 Correct 576 ms 21320 KB Output is correct
5 Correct 564 ms 9808 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 11344 KB Output is correct
2 Correct 109 ms 19784 KB Output is correct
3 Correct 111 ms 21388 KB Output is correct
4 Correct 732 ms 18216 KB Output is correct
5 Correct 368 ms 16148 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11344 KB Output is correct
2 Correct 853 ms 11456 KB Output is correct
3 Correct 201 ms 19580 KB Output is correct
4 Correct 616 ms 18116 KB Output is correct
5 Correct 570 ms 16664 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 13128 KB Output is correct
2 Correct 120 ms 12880 KB Output is correct
3 Correct 121 ms 22008 KB Output is correct
4 Correct 731 ms 28196 KB Output is correct
5 Correct 625 ms 18620 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 12880 KB Output is correct
2 Correct 998 ms 12880 KB Output is correct
3 Correct 273 ms 20808 KB Output is correct
4 Correct 799 ms 24884 KB Output is correct
5 Correct 676 ms 12880 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 16200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 15952 KB Output is correct
2 Execution timed out 1037 ms 18248 KB Time limit exceeded
3 Halted 0 ms 0 KB -