QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485523#4931. Comic BingePetroTarnavskyi#WA 0ms3540kbC++203.5kb2024-07-20 19:17:202024-07-20 19:17:21

Judging History

你现在查看的是最新测评结果

  • [2024-07-20 19:17:21]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3540kb
  • [2024-07-20 19:17:20]
  • 提交

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'