QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#549959 | #6403. Master of Polygon | pandapythoner | RE | 1ms | 4184kb | C++23 | 8.6kb | 2024-09-07 02:42:46 | 2024-09-07 02:42:48 |
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(234);
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);
}
rep(i, q) {
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 > 0 and pos < m - 1) {
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
*/
详细
Test #1:
score: 100
Accepted
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 YES YES YES NO YES
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: -100
Runtime Error
input:
20 200000 8838 9219 12190 11292 15953 7581 16690 6159 21104 5484 8978 1076 4354 1065 1261 676 12684 14159 15469 22416 13493 28027 15531 26837 18253 26053 26444 24253 22160 19958 24879 12856 28793 22156 25300 10245 14749 15078 12946 13942 26544 28338 18806 21279 5592 29200 20935 25253 28189 17513 215...