QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549963 | #6403. Master of Polygon | pandapythoner | WA | 1ms | 4184kb | C++23 | 8.6kb | 2024-09-07 03:04:56 | 2024-09-07 03:04:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)
mt19937 rnd(234234);
ld pi = atan2l(0, -1);
struct vec {
ld x, y;
vec() : x(0), y(0) {}
vec(ld x, ld y) : x(x), y(y) {}
ld length2() const {
return x * x + y * y;
}
ld length() const {
return sqrtl(length());
}
void rotate(ld alpha) {
ld asin = sinl(alpha), acos = cosl(alpha);
ld nx = x * acos - y * asin;
ld ny = y * acos + x * asin;
x = nx;
y = ny;
}
};
vec operator+(const vec& a, const vec& b) {
return vec(a.x + b.x, a.y + b.y);
}
vec operator-(const vec& a, const vec& b) {
return vec(a.x - b.x, a.y - b.y);
}
ld operator*(const vec& a, const vec& b) {
return a.x * b.x + a.y * b.y;
}
vec operator*(ld a, const vec& b) {
return vec{ a * b.x, a * b.y };
}
ld operator%(const vec& a, const vec& b) {
return a.x * b.y - a.y * b.x;
}
ld eps = 1e-9;
int sign(ld x) {
if (abs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
bool intersects(const vec& a, const vec& b, const vec& c, const vec& d, bool collinear_bad = false) {
if (abs((a - b) % (c - d)) < eps) {
if (collinear_bad) return false;
if (abs((b - a) % (c - a)) >= eps) return false;
if (max((b - a) * (c - a), (b - a) * (d - a)) < -eps) return false;
if (max((a - b) * (c - b), (a - b) * (d - b)) < -eps) return false;
return true;
}
if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) > 0) return false;
if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) > 0) return false;
return true;
}
vec intersect(const vec& a, const vec& b, const vec& c, const vec& d) {
vec t = a - b;
swap(t.x, t.y);
t.x = -t.x;
assert(abs(t * a - t * b) <= eps);
ld need = t * a;
ld start = t * c;
ld finish = t * d;
assert(min(start, finish) - eps <= need and need <= max(start, finish) + eps);
ld alpha = (need - start) / (finish - start);
vec result = (1 - alpha) * c + alpha * d;
assert(abs(t * result - need) < eps);
return result;
}
ld get_val(vec a, vec b, ld x) {
if (a.x > b.x) swap(a, b);
assert(a.x + eps < x and x + eps < b.x);
ld alpha = (x - a.x) / (b.x - a.x);
ld result = a.y * (1 - alpha) + b.y * alpha;
return result;
}
const int block_len = 300;
int n, q;
vector<pair<vec, vec>> poly;
vector<pair<vec, vec>> tasks;
ld cur_x = 0;
struct compare {
bool operator()(const tuple<vec, vec, int>& p, const tuple<vec, vec, int>& q) const {
auto [a, b, i] = p;
auto [c, d, j] = q;
ld yi = get_val(a, b, cur_x);
ld yj = get_val(c, d, cur_x);
if (abs(yi - yj) > eps) {
return yi < yj;
}
return i < j;
}
};
signed main() {
cerr << pi << endl;
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> q;
poly.resize(n);
rep(i, n) {
vec a;
cin >> a.x >> a.y;
poly[i].first = a;
poly[(n + i - 1) % n].second = a;
}
tasks.resize(q);
rep(i, q) {
cin >> tasks[i].first.x >> tasks[i].first.y >> tasks[i].second.x >> tasks[i].second.y;
}
ld alpha = rnd() % int(1e9) / (1e9) * 2 * pi;
// alpha = 0.02;
cerr << "alpha: " << alpha << endl;
rep(i, n) {
poly[i].first.rotate(alpha);
poly[i].second.rotate(alpha);
}
rep(i, q) {
tasks[i].first.rotate(alpha);
tasks[i].second.rotate(alpha);
}
vector<bool> result(q, true);
for (int l = 0; l < q; l += block_len) {
int r = min(q, l + block_len);
vector<ld> points;
rep(i, n) points.push_back(poly[i].first.x);
for (int i = l; i < r; i += 1) {
points.push_back(tasks[i].first.x);
points.push_back(tasks[i].second.x);
auto [a, b] = tasks[i];
for (int j = i + 1; j < r; j += 1) {
auto [c, d] = tasks[j];
if (intersects(a, b, c, d, true)) {
points.push_back(intersect(a, b, c, d).x);
}
}
}
sort(all(points));
int cur = 0;
for (int i = 1; i < len(points); i += 1) {
if (abs(points[i] - points[cur]) > eps) {
points[++cur] = points[i];
}
}
points.resize(cur + 1);
int m = len(points);
assert(m >= 2);
vector<vector<int>> to_insert(m - 1), to_erase(m - 1);
auto get_pos = [&](ld x) {
auto it = upper_bound(all(points), x + eps);
assert(it != points.begin());
int i = it - points.begin() - 1;
assert(abs(points[i] - x) < eps);
return i;
};
rep(i, n) {
auto [a, b] = poly[i];
int pa = get_pos(a.x), pb = get_pos(b.x);
assert(pa != pb);
if (pa > pb) swap(pa, pb);
to_insert[pa].push_back(i);
to_erase[pb - 1].push_back(i);
}
for (int i = l; i < r; i += 1) {
auto [a, b] = tasks[i];
int pa = get_pos(a.x), pb = get_pos(b.x);
assert(pa != pb);
if (pa > pb) swap(pa, pb);
to_insert[pa].push_back(n + i);
to_erase[pb - 1].push_back(n + i);
for (int j = l; j < r; j += 1) {
if (i == j) continue;
auto [c, d] = tasks[j];
if (intersects(a, b, c, d, true)) {
ld x = intersect(a, b, c, d).x;
int pos = get_pos(x);
if (pos > pa and pos < pb) {
to_erase[pos - 1].push_back(n + i);
to_insert[pos].push_back(n + i);
}
}
}
}
set<tuple<vec, vec, int>, compare> st;
vector<bool> inserted(n + q, false);
auto intersects_tuples = [&](const tuple<vec, vec, int>& p, const tuple<vec, vec, int>& q) {
auto& [a, b, i] = p;
auto& [c, d, j] = q;
return ((i >= n) != (j >= n)) and intersects(a, b, c, d);
};
function<void(int)> insert;
function<void(int)> erase;
function<void(decltype(st)::iterator)> check;
check = [&](decltype(st)::iterator it) {
if (it == st.end()) return;
if (it != st.begin()) {
if (intersects_tuples(*it, *prev(it))) {
--it;
}
}
if (it != st.end()) {
if (intersects_tuples(*it, *next(it))) {
int i = get<2>(*it);
if (i < n) {
it = next(it);
i = get<2>(*it);
}
assert(i >= n);
auto nit = it != st.begin() ? prev(it) : next(it);
inserted[i] = false;
result[i - n] = false;
st.erase(it);
check(nit);
}
}
};
erase = [&](int i) {
if (!inserted[i]) return;
vec a, b;
if (i < n) {
tie(a, b) = poly[i];
} else {
tie(a, b) = tasks[i - n];
}
auto it = st.find(make_tuple(a, b, i));
assert(it != st.end());
auto nit = it != st.begin() ? prev(it) : next(it);
st.erase(it);
inserted[i] = false;
check(nit);
};
insert = [&](int i) {
if (inserted[i]) return;
if (i >= n and !result[i - n]) return;
vec a, b;
if (i < n) {
tie(a, b) = poly[i];
} else {
tie(a, b) = tasks[i - n];
}
auto it = st.emplace(a, b, i).first;
inserted[i] = true;
check(it);
};
rep(i, m - 1) {
cur_x = (points[i] + points[i + 1]) / 2;
for (auto pos : to_insert[i]) insert(pos);
for (auto pos : to_erase[i]) erase(pos);
}
}
rep(i, q) {
if (!result[i]) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
return 0;
}
/*
4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4184kb
input:
4 6 1 1 4 1 4 4 1 4 0 2 2 0 0 1 1 1 0 0 5 5 2 2 4 2 2 2 3 2 5 1 0 2
output:
YES NO YES YES NO YES
result:
wrong answer expected YES, found NO [2nd token]