QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423654 | #5443. Security at Museums | u2x1 | WA | 1ms | 3588kb | C++20 | 4.9kb | 2024-05-28 14:41:18 | 2024-05-28 14:41:20 |
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; }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
struct Line { Pt s, t; };
bool ptOnSeg(Pt x, Line v) {
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) {
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) {
return (ptOnSeg(a.s, b) || ptOnSeg(a.t, b)
|| ptOnSeg(b.s, a) || ptOnSeg(b.t, a));
}
bool segInter_strict(Line a, Line b) {
return (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);
}
bool segInPoly(Line s, const 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, inferior = side(a, b, c) > 0;
for (auto x : {s.s, s.t}) {
if (inferior) {
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;
}
bool vis[201];
int dp[201];
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; segs.reserve(n*n);
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; };
auto cmp = [&](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::sort(all(segs), cmp);
std::vector<int> id(n); std::iota(all(id), 0);
std::sort(all(id), [&](int a, int b) { return polys[a] < polys[b]; });
lnt ret = 0;
const unsigned int mo = 998244353;
std::multiset<std::pair<int, int>, decltype(cmp)> ssegs(cmp);
for (auto x : segs) {
ssegs.emplace(x);
}
for (int _ = 0; _ < n; ++_) {
int u = id[_];
memset(dp, 0, sizeof(dp));
dp[u] = 1;
vis[u] = true;
for (auto it = ssegs.begin(); it != ssegs.end(); ) {
auto [a, b] = *it;
dp[b] = (dp[b] + dp[a]) % mo;
if (vis[a] || vis[b]) { it = ssegs.erase(it); }
else { ++it; }
}
ret = (ret + dp[u] - 1 + mo) % mo;
}
auto ksm = [&](lnt x, unsigned 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(); ) {
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]};
if (sign(a.t - a.s) - sign(b.t - b.s)) { break; }
if (sgn(det(a.t - a.s, b.t - b.s))) { break; }
if (!segInter(a, b)) { break; }
a.t = b.t;
++j;
}
for (int k = 1; ; ++k) {
if (k * (k + 1) / 2 == j - i) {
if (k == 1) { break; }
for (int w = 1; w < k; ++w) {
for (lnt z = w, c = 1, f = 1; z < k; ) {
ret = (ret - ksm(2, c) * f % mo) % mo;
f = (f * 2 + 1) % mo;
++z, ++c;
}
}
break;
}
}
i = j;
}
ret = (ret + mo) % mo;
std::cout << ret; NL;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3588kb
input:
7 0 20 40 0 40 20 70 50 50 70 30 50 0 50
output:
33
result:
wrong answer 1st numbers differ - expected: '56', found: '33'