QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417284#8669. 正方形计数Romeo35 776ms3868kbC++141.6kb2024-05-22 17:03:252024-05-22 17:03:26

Judging History

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

  • [2024-05-22 17:03:26]
  • 评测
  • 测评结果:35
  • 用时:776ms
  • 内存:3868kb
  • [2024-05-22 17:03:25]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cmath>
const int N = 8;
const int INF = 0x3f3f3f3f;
int read() {int x; return scanf("%d", &x), x;}
int n, m;
int _x[N + 5], _y[N + 5];
struct function
{
	int a, b, c; // ax + by + c >= 0
} t[N + 5], p[N + 5];
int get(int x)
{
//	printf("******%d******\n", x);
	int l = -INF, r = INF;
	for (int i = 1; i <= n; i ++ )
	{
		int a = p[i].a, b = p[i].b, c = p[i].c;
//		printf("%d %d %d\n", a, b, c);
		if (b == 0) if (a * x + c < 0) return 0;
		if (b > 0) l = std :: max(l, (int)std :: ceil(1.0 * ( - a * x - c) / b));
		if (b < 0) r = std :: min(r, (int)std :: floor(1.0 * (a * x + c) / (-b)));
		if (l > r) return 0; 
	}
//	printf("%d %d\n", l, r);
	return r - l + 1;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; i ++ ) _x[i] = read(), _y[i] = read(), m = std :: max(m, std :: max(_x[i], _y[i]));
	for (int i = 1; i <= n; i ++ )
	{
		int x1 = _x[i], y1 = _y[i], x2 = _x[i % n + 1], y2 = _y[i % n + 1];
		if (x1 == x2)
		{
			if (y1 < y2) t[i] = /* */ {1, 0, -x1};
			else t[i] = /* */ {-1, 0, x1};
		}
		else t[i] = /* */ {y2 - y1, x1 - x2, x2 * y1 - x1 * y2};
	}
	for (int i = 1; i <= n; i ++ ) p[i] = t[i];
	int res = 0;
	for (int a = 1; a <= m; a ++ )
	{
		for (int b = 0; b <= m; b ++ )
		{
//			int a = 1, b = 1;
			for (int i = 1; i <= n; i ++ ) p[i].c = t[i].c - std :: max({t[i].a * (0) + t[i].b * (0), t[i].a * ( - a) + t[i].b * ( - b), t[i].a * (b - a) + t[i].b * ( - a - b), t[i].a * (b) + t[i].b * ( - a)});
			for (int i = 0; i <= m; i ++ ) res += get(i);
		}
	}
	printf("%d", res);
	return 0;
}

/*
4
0 2
2 2
2 0
0 0
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

4
131 603
131 1828
1919 1828
1919 603

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

3
131 603
131 1828
1919 603

output:


result:


Subtask #3:

score: 15
Accepted

Test #11:

score: 15
Accepted
time: 0ms
memory: 3704kb

input:

8
0 13
4 15
15 15
15 6
13 1
12 0
5 0
0 6

output:

4047

result:

ok 1 number(s): "4047"

Test #12:

score: 15
Accepted
time: 0ms
memory: 3620kb

input:

8
0 4
1 15
2 15
15 14
15 4
14 0
1 0
0 2

output:

4200

result:

ok 1 number(s): "4200"

Test #13:

score: 15
Accepted
time: 0ms
memory: 3616kb

input:

5
7 15
15 13
15 0
3 0
0 15

output:

3635

result:

ok 1 number(s): "3635"

Test #14:

score: 15
Accepted
time: 1ms
memory: 3864kb

input:

8
0 12
2 14
7 15
13 15
15 10
15 1
8 0
0 0

output:

4511

result:

ok 1 number(s): "4511"

Test #15:

score: 15
Accepted
time: 0ms
memory: 3784kb

input:

6
0 11
3 15
7 15
15 12
10 0
0 0

output:

3006

result:

ok 1 number(s): "3006"

Test #16:

score: 15
Accepted
time: 1ms
memory: 3612kb

input:

5
0 0
0 2
1 2
2 1
2 0

output:

4

result:

ok 1 number(s): "4"

Subtask #4:

score: 20
Accepted

Dependency #3:

100%
Accepted

Test #17:

score: 20
Accepted
time: 507ms
memory: 3700kb

input:

8
49 299
144 300
300 260
250 15
115 0
30 0
23 19
0 85

output:

443602646

result:

ok 1 number(s): "443602646"

Test #18:

score: 20
Accepted
time: 776ms
memory: 3656kb

input:

8
0 133
103 300
130 300
257 294
297 227
300 150
277 40
161 4

output:

351466521

result:

ok 1 number(s): "351466521"

Test #19:

score: 20
Accepted
time: 442ms
memory: 3868kb

input:

8
76 286
114 300
300 300
300 205
291 0
47 0
4 57
2 235

output:

605026927

result:

ok 1 number(s): "605026927"

Test #20:

score: 20
Accepted
time: 555ms
memory: 3864kb

input:

8
0 102
40 274
282 300
300 234
267 0
34 0
6 57
0 86

output:

497330741

result:

ok 1 number(s): "497330741"

Test #21:

score: 20
Accepted
time: 634ms
memory: 3840kb

input:

7
0 288
156 300
212 300
265 176
300 86
278 0
0 36

output:

446722651

result:

ok 1 number(s): "446722651"

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #4:

100%
Accepted

Test #22:

score: 0
Time Limit Exceeded

input:

5
257 800
766 800
800 353
667 0
42 0

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%