oj.uz

Submission #1102801

# Submission time Handle Problem Language Result Execution time Memory
1102801 2024-10-19T01:13:57 Z vjudge1 Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 83968 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;
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;
}
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;
}
ld bi_search(const Polygon& B) {
	int cnt = 70;
	ld s = 0, e = L * 1.5;
	while (cnt--) {
		ld m = (s + e) * .5;
		//if (sweep(B, m)) s = m;
		if (F(B, m)) s = m;
		else e = 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;
	std::cout << bi_search(B) << "\n";
	return;
}
int main() { solve(); return 0; }//boj3346

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; }
      |                                     ~~~~~~~^~~~~~~~~
mobile.cpp: In function 'bool F(const Polygon&, const ld&)':
mobile.cpp:102:6: warning: variable 'vec' set but not used [-Wunused-but-set-variable]
  102 |  Pos vec = e - s;
      |      ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 1568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 1376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1352 KB Output is correct
2 Correct 75 ms 1364 KB Output is correct
3 Incorrect 72 ms 1564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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