QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#220159 | #5443. Security at Museums | hocky | WA | 1ms | 4188kb | C++20 | 4.8kb | 2023-10-19 22:49:04 | 2023-10-19 22:49:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long long LL;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> PLL;
#define fi first
#define se second
#define pb push_back
#define rep(i,a,b) for(int i = a;i < b;i++)
#define all(a) begin(a), end(a)
#define sz(a) (int) a.size()
#define trav(nx, v) for(auto &nx : v)
template <class T> int sgn(T x) {
return (x > 0) - (x < 0);
}
const double eps = 1e-9;
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T _x = 0, T _y = 0) : x(_x), y(_y) {
}
bool operator<(const P &other)const {
return tie(x, y) < tie(other.x, other.y);
}
bool operator==(const P &other)const {
return tie(x, y) == tie(other.x, other.y);
}
P operator+(P p) const {
return P(x + p.x, y + p.y);
}
P operator-(P p) const {
return P(x - p.x, y - p.y);
}
P operator*(T d) const {
return P(x * d, y * d);
}
P operator/(T d) const {
return P(x / d, y / d);
}
T cross(P p) const {
return x * p.y - y * p.x;
}
T dot(P p) const {
return x * p.x + y * p.y;
}
T cross(P a, P b) const {
return (a - *this).cross(b - (*this));
}
T dist2() const {
return x * x + y * y;
}
double dist() const {
return sqrt(double(dist2()));
}
P unit() const {
return *this / dist();
}
};
template <class P> bool segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b);
auto oc = a.cross(b, c), od = a.cross(b, d);
if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
return 1;
return 0;
}
typedef Point<double> PD;
double segDist(PD& s, PD & e, PD &p) {
if (s == e) return (p - s).dist();
auto d = (e - s).dist2(), t = min(d, max(.0, (p - s).dot(e - s )));
return ((p - s) * d - (e - s) * t).dist() / d;
}
template<class P> bool onSegment(P s, P e, P p) {
return segDist(s, e, p) < eps;
}
template<class P>
bool inPolygon(const vector <P> &p, P a, bool strict = true) {
int cnt = 0, n = sz(p);
rep(i, 0, n) {
P q = p[(i + 1) % n];
if (onSegment(p[i], q, a)) return !strict;
cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
}
return cnt;
}
int isBad[205][205];
template<class P>
int solve(int u, int v, const vector <P> &isi) {
if (u == v) return 0;
if (u > v) return solve(v, u, isi);
int &ret = isBad[u][v];
if (~ret) return ret;
int n = sz(isi);
rep(k, 0, n) {
if (k == u || k == v || (k + 1) % n == u || (k + 1) % n == v) continue;
auto &a = isi[k], &b = isi[(k + 1) % n];
auto &c = isi[u], &d = isi[v];
if (onSegment(c, d, a)) return ret = solve(u, k, isi) || solve(k, v, isi);
if (onSegment(c, d, b)) return ret = solve(u, (k + 1) % n, isi) || solve((k + 1) % n, v, isi);
auto res = segInter(a, b, c, d);
if (res) return ret = 1;
}
return ret = !inPolygon(isi, (isi[u] + isi[v]) / 2, false);
}
const ll MOD = 998244353;
typedef pair<int, int> PII;
typedef pair<PD, PII> Slope;
typedef array<int, 3> Container;
const int LIM = 200;
LL memo[2][LIM + 5][LIM + 5];
int main() {
memset(isBad, -1, sizeof(isBad));
cin.tie(0)->sync_with_stdio(0);
cout.tie(0);
int n;
cin >> n;
vector <PD> isi(n);
trav(cur, isi) cin >> cur.x >> cur.y;
rep(i, 0, n) rep(j, 0, n) isBad[i][j] = isBad[j][i] = solve(i, j, isi);
// rep(i,0,n) rep(j,0,n) cout << i << " " << j << " " << isBad[i][j] << endl;
vector <int> perm(n);
iota(all(perm), 0);
sort(all(perm), [&](int a, int b) {
return isi[a] < isi[b];
});
vector<Slope> slopes;
rep(i, 0, n) rep(j, i + 1, n) {
if (!isBad[perm[i]][perm[j]]) {
slopes.pb({isi[perm[j]] - isi[perm[i]], {perm[i], perm[j]}});
}
}
// Sort ccw
sort(all(slopes), [&](const Slope & a, const Slope & b) {
if (a.fi.cross(b.fi) == 0) {
if (isi[a.se.se].x != isi[b.se.se].x) return isi[a.se.se].x > isi[b.se.se].x;
if (isi[a.se.fi].x != isi[b.se.fi].x) return isi[a.se.fi].x > isi[b.se.fi].x;
}
return a.fi.cross(b.fi) > 0;
// Same slope case
});
rep(i, 0, n) memo[0][i][i] = memo[1][i][i] = 1;
trav(slope, slopes) {
int i = slope.se.fi, j = slope.se.se;
rep(k, 0, n) {
memo[0][i][k] = (memo[0][i][k] + memo[0][j][k]) % MOD;
}
}
sort(all(slopes), [&](const Slope & a, const Slope & b) {
if (a.fi.cross(b.fi) == 0) {
if (isi[a.se.se].x != isi[b.se.se].x) return isi[a.se.se].x > isi[b.se.se].x;
if (isi[a.se.fi].x != isi[b.se.fi].x) return isi[a.se.fi].x > isi[b.se.fi].x;
}
return a.fi.cross(b.fi) > 0;
// Same slope case
});
trav(slope, slopes) {
int i = slope.se.fi, j = slope.se.se;
rep(k, 0, n) {
memo[1][j][k] = (memo[1][j][k] + memo[1][i][k]) % MOD;
}
}
LL ans = 0;
rep(i, 0, n) rep(j, 0, n) {
ans += memo[0][i][j] * memo[1][j][i] % MOD;
}
cout << (ans - n + MOD) % MOD << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3948kb
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: 4064kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 4004kb
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: 4044kb
input:
4 -100 0 0 -100 100 0 0 100
output:
11
result:
ok 1 number(s): "11"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3944kb
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: 3888kb
input:
4 0 0 20 0 30 10 10 10
output:
11
result:
ok 1 number(s): "11"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3940kb
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: 3940kb
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: 4064kb
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: 4176kb
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: 3964kb
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: 4188kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
41
result:
wrong answer 1st numbers differ - expected: '44', found: '41'