QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419423 | #5443. Security at Museums | u2x1 | WA | 92ms | 3948kb | C++20 | 5.6kb | 2024-05-23 21:51:45 | 2024-05-23 21:51:47 |
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)) {
if (!ptOnSeg(b.t, a)) {
a.t = b.t;
}
++j;
} else { break; }
}
for (int k = 1; ; ++k) {
if (k * (k + 1) / 2 == j - i) {
if (k > 1) {
if (k > 3) { std::cout << k; exit(0); }
for (int w = 1; w < k; ++w) {
for (int z = w, c = 1, f = 1; z < k; ++z, ++c, f = f * 2 + 1) {
ret = (ret - ksm(2, c) * f % mo) % mo;
}
}
}
break;
}
assert(k <= n);
}
i = j - 1;
}
ret = (ret + 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: 3744kb
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: 3652kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
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: 3544kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3744kb
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: 3804kb
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: 3656kb
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: 3568kb
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: 3744kb
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: 3660kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3656kb
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: 3632kb
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: 0
Accepted
time: 0ms
memory: 3664kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
44
result:
ok 1 number(s): "44"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
16 0 0 20 0 20 10 40 10 40 20 60 20 60 30 70 30 70 40 50 40 50 30 30 30 30 20 10 20 10 10 0 10
output:
407
result:
ok 1 number(s): "407"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
12 0 0 400 0 400 500 0 500 0 200 200 200 200 300 100 300 100 400 300 400 300 100 0 100
output:
51
result:
ok 1 number(s): "51"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
10 0 500 -10 20 -350 350 -20 0 -350 -350 0 -20 350 -350 20 0 350 350 10 20
output:
93
result:
ok 1 number(s): "93"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
16 0 0 10 -5 20 0 30 15 40 0 45 10 40 20 25 30 40 40 30 45 20 40 10 25 0 40 -5 30 0 20 15 10
output:
247
result:
ok 1 number(s): "247"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
8 100 90 90 100 -90 100 -100 90 -100 -90 -90 -100 90 -100 100 -90
output:
247
result:
ok 1 number(s): "247"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
8 0 0 10 100 90 100 100 0 100 201 90 101 10 101 0 201
output:
31
result:
ok 1 number(s): "31"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
8 0 0 100 100 900 100 1000 0 1000 210 900 110 100 110 0 210
output:
31
result:
ok 1 number(s): "31"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 1000000 -1000000 1000000 1000000 -1000000 -1000000
output:
4
result:
ok 1 number(s): "4"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
4 1000000 -1000000 1000000 1000000 1 0 -1000000 -1000000
output:
7
result:
ok 1 number(s): "7"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
4 1000000 -1000000 1000000 1000000 0 1 -1000000 -1000000
output:
11
result:
ok 1 number(s): "11"
Test #25:
score: 0
Accepted
time: 92ms
memory: 3948kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
982924531
result:
ok 1 number(s): "982924531"
Test #26:
score: 0
Accepted
time: 91ms
memory: 3836kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
491462169
result:
ok 1 number(s): "491462169"
Test #27:
score: -100
Wrong Answer
time: 44ms
memory: 3872kb
input:
200 -1000000 0 -984589 0 -959090 -1000000 -939997 0 -920698 -1000000 -903689 0 -878269 -1000000 -856526 0 -835872 -1000000 -824921 0 -802874 -1000000 -775273 0 -762503 -1000000 -736648 0 -723628 -1000000 -700062 0 -677324 -1000000 -655520 0 -638093 -1000000 -616069 0 -596730 -1000000 -578522 0 -5610...
output:
100
result:
wrong answer 1st numbers differ - expected: '766756066', found: '100'