QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485721#4942. Robust DefensePetroTarnavskyiWA 1402ms9800kbC++204.5kb2024-07-21 02:37:482024-07-21 02:37:48

Judging History

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

  • [2024-07-21 02:37:48]
  • 评测
  • 测评结果:WA
  • 用时:1402ms
  • 内存:9800kb
  • [2024-07-21 02:37:48]
  • 提交

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<pair<Pt, int>>& v, const Pt& u)
{
	sort(ALL(v), [&](pair<Pt, int> pp, pair<Pt, int> qq)
	{
		const Pt& p = pp.F - o;
		const Pt& q = qq.F - 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 >> m >> n >> s;
	vector<Pt> q(m), p(n);
	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));
	vector<pair<Pt, int>> pp(n);
	FOR(i, 0, n)
		pp[i] = {p[i], 0};
	polarSortAround(q[0], pp, {1, 0});
	FOR(i, 0, n)
		p[i] = pp[i].F;
	FOR(i, 0, n)
		cerr << p[i].x << " " << p[i].y << "\n";
	vector ok(n, VI(n)), cnt(n, VI(n)), cnt2(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]++;
			}
			FOR(k, j + 1, n)
			{
				if (k != i && orient(p[i], p[j], p[k]) <= 0 && orient(q[0], p[i], p[k]) >= 0 && orient(q[0], p[j], p[k]) < 0)
					cnt2[i][j]++;
			}
		}
	}
	VI pw(n);
	pw[0] = 1;
	FOR(i, 1, n)
		pw[i] = mult(pw[i - 1], sub(1, s));
	int ans = 0;
	vector<vector<pair<Pt, int>>> p1(n), p2(n);
	FOR(j, 0, n)
	{
		FOR(i, 0, n)
		{
			LL ori = orient(q[0], p[j], p[i]);
			if (i < j && ori <= 0)
				p1[j].PB({p[i], i});
			if (i > j && ori >= 0)
				p2[j].PB({p[i], i});
		}
		polarSortAround(p[j], p1[j], p[j] - q[0]);
		polarSortAround(p[j], p2[j], p[j] - q[0]);
	}
	FOR(i, 0, n)
	{
		
		vector dp(n, VI(n));
		FOR(j, i + 1, n)
			dp[i][j] = mult(mult(s, pw[cnt[i][j] + i]), ok[i][j]);
		
		FOR(j, i + 1, n)
		{
			int ptr = 0;
			int sum = 0;
			for (auto [pk, k] : p2[j])
			{
				while (ptr < SZ(p1[j]) && orient(p1[j][ptr].F, p[j], pk) > 0)
				{
					//cerr << "tu " << i << " " << j << " " << k << " " << p1[j][ptr].S << endl;
					updAdd(sum, dp[p1[j][ptr].S][j]);
					ptr++;
				}
				dp[j][k] = mult(sum, mult(mult(s, pw[cnt[j][k]]), ok[j][k]));
				if (orient(p[j], p[k], p[i]) > 0)
				{
					updAdd(ans, mult(dp[j][k], mult(mult(s, pw[cnt2[k][i]]), ok[k][i])));
				}
			}
		}
		//cerr << i << " " << mult(16, ans) << "\n";
	}
	FOR(i, 0, n)
		FOR(j, i + 1, 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: 100
Accepted
time: 0ms
memory: 3596kb

input:

1 4 50
0 0
-1 0
3 0
0 1
2 -1

output:

686292993

result:

ok single line: '686292993'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3 5 20
3 0
1 3
5 3
0 0
0 6
6 0
6 6
3 3

output:

771443236

result:

ok single line: '771443236'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

1 2 3
4 5
7 9
-2 -3

output:

184375732

result:

ok single line: '184375732'

Test #4:

score: -100
Wrong Answer
time: 1402ms
memory: 9800kb

input:

500 500 47
7 19
16 17
20 13
1 10
17 9
5 23
12 2
15 12
16 8
11 8
8 12
3 2
11 13
23 0
3 23
13 10
9 12
11 5
8 18
6 0
6 20
3 9
1 21
13 18
5 11
9 15
8 17
6 18
1 8
4 24
7 14
11 11
2 9
8 9
23 3
17 15
21 10
19 7
13 16
0 10
0 7
6 17
11 9
9 4
1 15
21 12
1 24
20 7
21 7
20 0
10 3
3 24
2 12
18 11
20 5
14 20
10 4...

output:

606513684

result:

wrong answer 1st lines differ - expected: '963504722', found: '606513684'