QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485523 | #4931. Comic Binge | PetroTarnavskyi# | WA | 0ms | 3540kb | C++20 | 3.5kb | 2024-07-20 19:17:20 | 2024-07-20 19:17:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 998244353;
int add(int a, int b)
{
return a + b < mod ? a + b : a + b - mod;
}
void updAdd(int& a, int b)
{
a += b;
if (a >= mod)
a -= mod;
}
int sub(int a, int b)
{
return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
return (LL)a * b % mod;
}
int binpow(int a, int n)
{
int res = 1;
while (n)
{
if (n & 1)
res = mult(res, a);
a = mult(a, a);
n /= 2;
}
return res;
}
struct Pt
{
int x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
};
LL sq(const Pt& p)
{
return (LL)p.x * p.x + (LL)p.y * p.y;
}
int sgn(LL x)
{
return (0 < x) - (x < 0);
}
LL dot(const Pt& p, const Pt& q)
{
return (LL)p.x * q.x + (LL)p.y * q.y;
}
LL cross(const Pt& p, const Pt& q)
{
return (LL)p.x * q.y - (LL)p.y * q.x;
}
LL orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p);
}
void polarSortAround(const Pt& o, vector<Pt>& v, const Pt& u)
{
sort(ALL(v), [&](Pt p, Pt q)
{
p = p - o;
q = q - o;
bool hp = cross(u, p) > 0 || (cross(u, p) == 0 && dot(u, p) > 0);
bool hq = cross(u, q) > 0 || (cross(u, q) == 0 && dot(u, q) > 0);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(dot(a - p, b - p)) <= 0;
}
bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, s;
cin >> n >> m >> s;
vector<Pt> q(n), p(m);
for (Pt& qi : q)
cin >> qi.x >> qi.y;
for (Pt& pi : p)
cin >> pi.x >> pi.y;
s = mult(s, binpow(100, mod - 2));
polarSortAround(q[0], p, {1, 0});
vector ok(n, VI(n)), cnt(n, VI(n));
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (i == j)
continue;
ok[i][j] = 1;
FOR(k, 0, m)
{
ok[i][j] &= !(orient(p[i], p[j], q[k]) <= 0 && !onSegment(p[i], p[j], q[k]));
}
FOR(k, 0, n)
{
if (k != i && k != j && orient(p[i], p[j], p[k]) <= 0 && orient(q[0], p[i], p[k]) >= 0 && orient(q[0], p[j], p[k]) < 0)
cnt[i][j]++;
}
}
}
VI pw(n);
pw[0] = 1;
FOR(i, 1, n)
pw[i] = mult(pw[i - 1], sub(1, s));
int ans = 0;
FOR(i, 0, n)
{
vector dp(n, VI(n));
FOR(j, 0, n)
dp[i][j] = mult(mult(s, pw[cnt[i][j] + i]), ok[i][j]);
FOR(j, 0, n)
{
FOR(k, j + 1, n)
{
FOR(l, 0, j)
{
if (orient(p[l], p[j], p[k]))
{
updAdd(dp[j][k], dp[l][j]);
}
}
dp[j][k] = mult(dp[j][k], mult(mult(s, pw[cnt[j][k]]), ok[j][k]));
updAdd(ans, mult(dp[j][k], mult(mult(s, pw[cnt[k][i]]), ok[k][i])));
}
}
}
FOR(i, 0, n)
FOR(j, 0, n)
{
if (i == j)
continue;
bool good = true;
FOR(k, 0, m)
good &= onSegment(p[i], p[j], q[k]);
int c = 0;
FOR(k, 0, n)
{
if (k != i && k != j && !onSegment(p[i], p[j], p[k]))
{
c++;
}
}
if (good)
{
updAdd(ans, mult(mult(s, s), pw[c]));
}
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3540kb
input:
6 3 1 1 1 1 2 1 5 3 3 7 4
output:
0
result:
wrong answer 1st lines differ - expected: '13', found: '0'