QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419409 | #5443. Security at Museums | u2x1 | WA | 1ms | 3820kb | C++20 | 5.5kb | 2024-05-23 21:41:03 | 2024-05-23 21:41:04 |
Judging History
answer
#include "bits/stdc++.h"
#define all(x) x.begin(), x.end()
#define NL std::cout << '\n'
using lnt = long long;
const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 61;
using db = double; const db eps = 1e-12;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }
struct Pt { db x, y; };
std::istream& operator>>(std::istream& is, Pt &p) {
int x, y; std::cin >> x >> y;
p.x = x; p.y = y; return is;
}
std::ostream& operator<<(std::ostream& os, Pt p) {
return os << "(" << p.x << "," << p.y << ")";
}
Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator!=(Pt a, Pt b) { return sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
db dis2(Pt a, Pt b) { return dot(a-b, a-b); }
db dis(Pt a, Pt b) { return std::sqrt(dis2(a, b)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
Pt rot90(Pt a) { return {-a.y, a.x}; }
Pt rot(Pt a, db t) {
return { a.x * std::cos(t) - a.y * std::sin(t)
, a.x * std::sin(t) + a.y * std::cos(t) };
}
Pt unit(Pt a) {
db d = dis(a, {0, 0});
return sgn(d) ? a/d : Pt{0, 0};
}
struct Line { Pt s, t; };
bool ptOnSeg(Pt x, Line v) {
if (v.s == v.t) { return sgn(dis2(v.s, x)) == 0; }
return sgn(det(v.s - x, v.t - x)) == 0
&& sgn(dot(v.s - x, v.t - x)) <= 0;
}
bool ptOnSegStrict(Pt x, Line v) {
if (v.s == v.t) { return sgn(dis2(v.s, x)) == 0; }
return sgn(det(v.s - x, v.t - x)) == 0
&& sgn(dot(v.s - x, v.t - x)) < 0;
}
bool segInter(Line a, Line b) {
if (sgn(det(b.s-a.s, a.t-a.s)) * sgn(det(b.t-a.s, a.t-a.s)) == -1
&& sgn(det(a.s-b.s, b.t-b.s)) * sgn(det(a.t-b.s, b.t-b.s)) == -1) {
return true;
}
if (ptOnSeg(a.s, b) || ptOnSeg(a.t, b)
|| ptOnSeg(b.s, a) || ptOnSeg(b.t, a)) {
return true;
}
return false;
}
bool segInter_strict(Line a, Line b) {
if (sgn(det(b.s-a.s, a.t-a.s)) * sgn(det(b.t-a.s, a.t-a.s)) == -1
&& sgn(det(a.s-b.s, b.t-b.s)) * sgn(det(a.t-b.s, b.t-b.s)) == -1) {
return true;
}
return false;
}
bool segInPoly(Line s, std::vector<Pt> &v) {
const int n = v.size();
for (int i = 0; i < n; ++i) {
const Pt a = v[i], b = v[(i+1) % n], c = v[(i+2) % n];
if (segInter_strict(s, {a, b})) { return false; }
if (ptOnSeg(b, s)) {
bool ok = true, acute = side(a, b, c) > 0;
for (auto x : {s.s, s.t}) {
if (acute) {
ok &= side(a, b, x) >= 0 && side(b, c, x) >= 0;
} else {
ok &= side(a, b, x) >= 0 || side(b, c, x) >= 0;
}
}
if (!ok) { return false; }
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0);
int n; std::cin >> n;
std::vector<Pt> polys(n);
for (int i = 0; i < n; ++i) { std::cin >> polys[i]; }
std::vector<std::pair<int, int>> segs;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (!segInPoly({polys[i], polys[j]}, polys)) { continue; }
segs.push_back({i, j});
segs.push_back({j, i});
}
}
auto sign = [](Pt u) -> int { return (u.y > eps || (sgn(u.y) == 0 && u.x > eps)) ? 1 : -1; };
std::sort(all(segs), [&](auto i, auto j) {
Line a = {polys[i.first], polys[i.second]}, b = {polys[j.first], polys[j.second]};
int dir = sign(a.t-a.s) - sign(b.t-b.s);
if (dir) { return dir > 0; }
dir = sgn(det(a.t-a.s, b.t-b.s));
if (dir) { return dir > 0; }
dir = sgn(det(a.t-a.s, b.t-a.s));
if (dir) { return dir < 0; }
dir = sgn(dot(a.t-a.s, b.t-a.t));
return dir > 0;
});
std::vector<int> id(n); std::iota(all(id), 0);
std::sort(all(id), [&](int a, int b) { return sign(polys[a] - polys[b]) == -1; });
lnt ret = 0;
const int mo = 998244353;
std::basic_string<bool> vis(n, 0);
for (int _ = 0; _ < n; ++_) {
int u = id[_];
std::vector<int> dp(n);
dp[u] = 1;
for (auto [a, b] : segs) {
if (vis[a] || vis[b]) { continue; }
dp[b] = (dp[b] + dp[a]) % mo;
}
ret = (ret + dp[u] - 1 + mo) % mo;
vis[u] = true;
}
auto ksm = [&](lnt x, int e) {
lnt ret = 1;
while (e) {
if (e & 1) { ret = ret * x % mo; }
x = x * x % mo; e >>= 1;
}
return ret;
};
for (int i = 0; i < segs.size(); ++i) {
Line a = {polys[segs[i].first], polys[segs[i].second]};
if (sign(a.t - a.s) == -1) { break; }
int j = i + 1;
while (j < segs.size()) {
Line b = {polys[segs[j].first], polys[segs[j].second]};
int dir = sign(a.t - a.s) - sign(b.t - b.s);
if (dir) { break; }
dir = sgn(det(a.t - a.s, b.t - b.s));
if (dir) { break; }
if (segInter(a, b)) {
++j;
} else { break; }
}
for (int k = 1; ; ++k) {
if (k * (k + 1) / 2 == j - i) {
if (k > 1) {
for (int w = 1; w < k; ++w) {
for (int z = w, c = 1, f = 1; z < k; ++z, ++c, f = f * 2 + 1) {
ret -= ksm(2, c) * f;
}
}
}
break;
}
assert(k <= n);
}
i = j - 1;
}
ret = (ret % mo + mo) % mo;
std::cout << ret; NL;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3808kb
input:
7 0 20 40 0 40 20 70 50 50 70 30 50 0 50
output:
56
result:
ok 1 number(s): "56"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 0 0 -10 0 -10 -10 0 -10
output:
11
result:
ok 1 number(s): "11"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
4 -100 0 0 -100 100 0 0 100
output:
11
result:
ok 1 number(s): "11"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 0 0 10 5 20 0 10 10
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4 0 0 20 0 30 10 10 10
output:
11
result:
ok 1 number(s): "11"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
4 -100 -10 100 -10 100 10 -100 10
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
4 0 0 100 0 60 30 0 30
output:
11
result:
ok 1 number(s): "11"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
7 0 0 10 10 20 0 30 11 20 22 10 11 0 22
output:
44
result:
ok 1 number(s): "44"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 0 0 10 10 20 0 30 10 40 0 40 21 30 11 20 21 10 11 0 21
output:
93
result:
ok 1 number(s): "93"
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
56
result:
wrong answer 1st numbers differ - expected: '44', found: '56'