QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#417284 | #8669. 正方形计数 | Romeo | 35 | 776ms | 3868kb | C++14 | 1.6kb | 2024-05-22 17:03:25 | 2024-05-22 17:03:26 |
Judging History
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%