QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73930 | #5443. Security at Museums | yuto1115 | WA | 2ms | 3512kb | C++17 | 17.7kb | 2023-01-29 16:18:53 | 2023-01-29 16:18:54 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SORT(a) sort(all(a));
#define REV(a) reverse(all(a));
#define SZ(a) int(a.size())
#define popcount(x) __builtin_popcountll(x)
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ppf pop_front
#define ppb pop_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0);
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vlp = vector<LP>;
using vvlp = vector<vlp>;
template<class T>
using PQ = priority_queue<T>;
template<class T>
using PQrev = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }
template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }
template<class S, class T, class U>
istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }
template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &t: v) { is >> t; }
return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const deque<T> &v) {
os << '[';
rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
ostream &operator<<(ostream &os, const set<T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
os << '{';
auto it = st.begin();
while (it != st.end()) {
os << (it == st.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T, class U>
ostream &operator<<(ostream &os, const map<T, U> &mp) {
os << '{';
auto it = mp.begin();
while (it != mp.end()) {
os << (it == mp.begin() ? "" : ", ") << *it;
it++;
}
return os << '}';
}
template<class T>
void vecout(const vector<T> &v, char div = '\n') {
rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}
template<class T>
bool constexpr chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void scan() {}
template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
cin >> head;
scan(tail...);
}
template<class T>
void print(const T &t) { cout << t << '\n'; }
template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
template<class... T>
void fin(const T &... a) {
print(a...);
exit(0);
}
template<class T>
vector<T> &operator+=(vector<T> &v, T x) {
for (T &t: v) t += x;
return v;
}
template<class T>
vector<T> &operator-=(vector<T> &v, T x) {
for (T &t: v) t -= x;
return v;
}
template<class T>
vector<T> &operator*=(vector<T> &v, T x) {
for (T &t: v) t *= x;
return v;
}
template<class T>
vector<T> &operator/=(vector<T> &v, T x) {
for (T &t: v) t /= x;
return v;
}
struct Init_io {
Init_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << boolalpha << fixed << setprecision(15);
cerr << boolalpha << fixed << setprecision(15);
}
} init_io;
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;
void rearrange(const vi &) {}
template<class T, class... Tail>
void rearrange(const vi &ord, vector<T> &head, Tail &...tail) {
assert(ord.size() == head.size());
vector<T> ori = head;
rep(i, ord.size()) head[i] = ori[ord[i]];
rearrange(ord, tail...);
}
template<class T, class... Tail>
void sort_by(vector<T> &head, Tail &... tail) {
vi ord(head.size());
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) { return head[i] < head[j]; });
rearrange(ord, head, tail...);
}
bool in_rect(int i, int j, int h, int w) {
return 0 <= i and i < h and 0 <= j and j < w;
}
template<class T, class S>
vector<T> cumsum(const vector<S> &v, bool shift_one = true) {
int n = v.size();
vector<T> res;
if (shift_one) {
res.resize(n + 1);
rep(i, n) res[i + 1] = res[i] + v[i];
} else {
res.resize(n);
if (n) {
res[0] = v[0];
rep(i, 1, n) res[i] = res[i - 1] + v[i];
}
}
return res;
}
vvi graph(int n, int m, bool directed = false, int origin = 1) {
vvi G(n);
rep(_, m) {
INT(u, v);
u -= origin, v -= origin;
G[u].pb(v);
if (!directed) G[v].pb(u);
}
return G;
}
template<class T>
vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) {
vector<vector<pair<int, T>>> G(n);
rep(_, m) {
int u, v;
T w;
scan(u, v, w);
u -= origin, v -= origin;
G[u].eb(v, w);
if (!directed) G[v].eb(u, w);
}
return G;
}
template<int mod>
class modint {
ll x;
public:
constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {}
static constexpr int get_mod() { return mod; }
constexpr int val() const { return x; }
constexpr modint operator-() const { return modint(-x); }
constexpr modint &operator+=(const modint &a) {
if ((x += a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator++() { return *this += 1; }
constexpr modint &operator-=(const modint &a) {
if ((x += mod - a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator--() { return *this -= 1; }
constexpr modint &operator*=(const modint &a) {
(x *= a.val()) %= mod;
return *this;
}
constexpr modint operator+(const modint &a) const {
modint res(*this);
return res += a;
}
constexpr modint operator-(const modint &a) const {
modint res(*this);
return res -= a;
}
constexpr modint operator*(const modint &a) const {
modint res(*this);
return res *= a;
}
constexpr modint pow(ll t) const {
modint res = 1, a(*this);
while (t > 0) {
if (t & 1) res *= a;
t >>= 1;
a *= a;
}
return res;
}
template<int m>
friend istream &operator>>(istream &, modint<m> &);
// for prime mod
constexpr modint inv() const { return pow(mod - 2); }
constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); }
constexpr modint operator/(const modint &a) const {
modint res(*this);
return res /= a;
}
// constraints : mod = 2 or val = 0 or val^((mod-1)/2) ≡ 1
// mod is prime
// time complexity : O(log^2 p)
// reference : https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp
modint sqrt() const {
if (x < 2) return x;
assert(this->pow((mod - 1) >> 1).val() == 1);
modint b = 1;
while (b.pow((mod - 1) >> 1).val() == 1) b += 1;
ll m = mod - 1, e = 0;
while (~m & 1) m >>= 1, e += 1;
modint X = this->pow((m - 1) >> 1);
modint Y = (*this) * X * X;
X *= *this;
modint Z = b.pow(m);
while (Y.val() != 1) {
ll j = 0;
modint t = Y;
while (t.val() != 1) {
j += 1;
t *= t;
}
Z = Z.pow(1LL << (e - j - 1));
X *= Z;
Z *= Z;
Y *= Z;
e = j;
}
return X;
}
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
template<int mod>
istream &operator>>(istream &is, modint<mod> &a) {
ll x;
is >> x;
a = modint<mod>(x);
return is;
}
template<int mod>
constexpr ostream &operator<<(ostream &os, const modint<mod> &a) { return os << a.val(); }
template<int mod>
constexpr bool operator==(const modint<mod> &a, const modint<mod> &b) { return a.val() == b.val(); }
template<int mod>
constexpr bool operator!=(const modint<mod> &a, const modint<mod> &b) { return a.val() != b.val(); }
template<int mod>
constexpr modint<mod> &operator++(modint<mod> &a) { return a += 1; }
template<int mod>
constexpr modint<mod> &operator--(modint<mod> &a) { return a -= 1; }
using mint = modint998244353;
using vm = vector<mint>;
using vvm = vector<vm>;
using point = LP;
ll cross(const point &a, const point &b) {
return a.first * b.second - a.second * b.first;
}
ll dot(const point &a, const point &b) {
return a.first * b.first + a.second * b.second;
}
ll norm(const point &p) {
return p.first * p.first + p.second * p.second;
}
int sgn(ll l) {
if (l < 0) return -1;
if (l == 0) return 0;
return 1;
}
int ccw(const point &a, const point &b, const point &c) {
// 1 -> c is upper than line(a,b)
// -1 -> c is lower than line(a,b)
// 2 -> in order [a,b,c]
// -2 -> in order [c,a,b]
// 0 -> in order [a,c,b]
point nb = {b.first - a.first, b.second - a.second};
point nc = {c.first - a.first, c.second - a.second};
if (sgn(cross(nb, nc))) return sgn(cross(nb, nc));
if (sgn(dot(nb, nc)) < 0) return -2;
if (sgn(norm(nc) - norm(nb)) > 0) return 2;
return 0;
}
struct segment {
point a, b;
segment(point a = point(), point b = point()) : a(a), b(b) {}
bool online(const point &p) const { return !ccw(a, b, p); }
};
ostream &operator<<(ostream &os, const segment &l) { return os << '{' << l.a << ',' << l.b << '}'; }
bool intersect(const segment &l, const segment &m) {
return ccw(l.a, l.b, m.a) * ccw(l.a, l.b, m.b) <= 0 &&
ccw(m.a, m.b, l.a) * ccw(m.a, m.b, l.b) <= 0;
}
// [-pi, pi)
// no (0, 0)
bool arg_cmp(const LP &a, const LP &b) {
int ua = a.second > 0 or (a.second == 0 and a.first > 0);
int ub = b.second > 0 or (b.second == 0 and b.first > 0);
if (ua == ub) {
ll cross = a.first * b.second - a.second * b.first;
return cross > 0;
} else {
return ua < ub;
}
}
class binomial_coefficient {
public:
vector<mint> fact, ifact;
binomial_coefficient(int n) : fact(n + 1), ifact(n + 1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * ifact[k] * ifact[n - k];
}
mint P(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * ifact[n - k];
}
mint naive(mint n, int k) {
mint res = 1;
rep(i, k) {
res *= n - i;
res /= i + 1;
}
return res;
}
mint naive_P(mint n, int k) {
mint res = 1;
rep(i, k) {
res *= n - i;
}
return res;
}
} binom(1000);
int main() {
INT(n);
vl x(n), y(n);
rep(i, n) scan(x[i], y[i]);
vector<point> pt(n);
rep(i, n) pt[i] = {x[i], y[i]};
vvi dir(n, vi(n, -1));
{
vector<tuple<int, int, LP>> tmp;
rep(i, n) rep(j, n) {
if (i == j) continue;
tmp.eb(i, j, LP{x[j] - x[i], y[j] - y[i]});
}
sort(all(tmp), [](auto a, auto b) { return arg_cmp(get<2>(a), get<2>(b)); });
int now = -1;
rep(i, SZ(tmp)) {
if (i == 0 or arg_cmp(get<2>(tmp[i - 1]), get<2>(tmp[i]))) ++now;
dir[get<0>(tmp[i])][get<1>(tmp[i])] = now;
}
}
debug(dir);
vvi ok(n, vi(n, true));
rep(i, n) rep(j, n) {
if (i == j) continue;
rep(_, 2) {
int a = (i + n - 1) % n;
int b = (i + 1) % n;
if (dir[i][b] <= dir[i][a]) {
ok[i][j] &= dir[i][b] <= dir[i][j] and dir[i][j] <= dir[i][a];
} else {
ok[i][j] &= dir[i][b] <= dir[i][j] or dir[i][j] <= dir[i][a];
}
swap(i, j);
}
segment s(pt[i], pt[j]);
rep(k, n) {
int a = k;
int b = (k + 1) % n;
if (a == i or a == j) continue;
if (b == i or b == j) continue;
if (s.online(pt[a])) continue;
if (s.online(pt[b])) continue;
segment t(pt[a], pt[b]);
ok[i][j] &= !intersect(s, t);
}
for (int k = (i + 1) % n; k != j; k = (k + 1) % n) {
if (!s.online(pt[k])) continue;
if (ccw(pt[i], pt[j], pt[(k + 1) % n]) == 1) ok[i][j] = false;
}
for (int k = (j + 1) % n; k != i; k = (k + 1) % n) {
if (!s.online(pt[k])) continue;
if (ccw(pt[i], pt[j], pt[(k + 1) % n]) == -1) ok[i][j] = false;
}
}
mint ans;
auto convex_low = [&](int s) -> vm {
vp eg;
rep(i, n) rep(j, n) if (i != j) eg.eb(i, j);
sort(all(eg),
[&](P a, P b) {
auto [ai, aj] = a;
auto [bi, bj] = b;
if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] < dir[bi][bj];
if (x[ai] != x[bi]) return x[ai] < x[bi];
return y[ai] < y[bi];
});
vm dp(n);
dp[s] = 1;
for (auto [i, j]: eg) {
if (!ok[i][j]) continue;
if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
dp[j] += dp[i];
}
return dp;
};
auto convex_up = [&](int s) -> vm {
vp eg;
rep(i, n) rep(j, n) if (i != j) eg.eb(i, j);
sort(all(eg),
[&](P a, P b) {
auto [ai, aj] = a;
auto [bi, bj] = b;
if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] > dir[bi][bj];
if (x[ai] != x[bi]) return x[ai] < x[bi];
return y[ai] < y[bi];
});
vm dp(n);
dp[s] = 1;
for (auto [i, j]: eg) {
if (!ok[i][j]) continue;
if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
dp[j] += dp[i];
}
return dp;
};
rep(s, n) {
vm dpl = convex_low(s);
vm dpu = convex_up(s);
debug(s);
debug(dpl);
debug(dpu);
rep(t, n) {
if (s == t) continue;
ans += dpl[t] * dpu[t];
}
}
rep(s, n) rep(t, s + 1, n) {
if (!ok[s][t]) continue;
int cnt = 0;
rep(i, n) {
if (i == s or i == t) continue;
segment now(pt[s], pt[t]);
if (now.online(pt[i])) ++cnt;
}
rep(i, 1, cnt + 1) {
mint now = binom(cnt, i);
now *= mint(3).pow(i);
ans -= now - 1;
debug(s, t, now);
}
}
fin(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
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: 2ms
memory: 3392kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
4 0 0 -10 0 -10 -10 0 -10
output:
11
result:
ok 1 number(s): "11"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3436kb
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: 3384kb
input:
4 0 0 10 5 20 0 10 10
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3412kb
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: 3356kb
input:
4 -100 -10 100 -10 100 10 -100 10
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
4 0 0 100 0 60 30 0 30
output:
11
result:
ok 1 number(s): "11"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3336kb
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: 3512kb
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: 2ms
memory: 3432kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
43
result:
wrong answer 1st numbers differ - expected: '44', found: '43'