QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#23809 | #2959. Antialiasing | George_Plover# | WA | 6ms | 4088kb | C++20 | 2.9kb | 2022-03-19 15:48:26 | 2022-04-30 04:10:18 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 205, Q = 2005;
int n, q;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
class point {
public:
int x, y;
void read() {
scanf("%d%d", &x, &y);
x = x * 2 + 1, y = y * 2 + 1;
}
} a[N];
class frac {
public:
ll x, y;
void sp() {
ll d = gcd(x, y);
x /= d, y /= d;
if (y < 0) {
y = -y, x = -x;
}
assert(y);
}
frac(ll _x, ll _y) {
x = _x;
y = _y;
sp();
}
frac operator+(const frac &rhs) const {
return frac(x * rhs.y + y * rhs.x, y * rhs.y);
}
frac operator-(const frac &rhs) const {
return frac(x * rhs.y - y * rhs.x, y * rhs.y);
}
frac operator*(const frac &rhs) const { return frac(x * rhs.x, y * rhs.y); }
frac operator/(const frac &rhs) const { return frac(x * rhs.y, y * rhs.x); }
bool operator<(const frac &rhs) const { return (*this - rhs).x < 0; }
void print() { printf("%lld/%lld", x, y); }
};
class seg {
public:
frac l, r;
seg(frac _l, frac _r) : l(_l), r(_r) {}
bool operator<(const seg &rhs) const { return l < rhs.l; }
void print() {
l.print();
printf("~");
r.print();
printf(", ");
}
};
vector<seg> segs[Q];
void put(point p1, point p2) {
if (p1.x > p2.x) swap(p1, p2);
rep(x, p1.x, p2.x - 1) {
frac l = frac(p1.y, 1) + frac((x - p1.x) * (p2.y - p1.y), p2.x - p1.x);
frac r =
frac(p1.y, 1) + frac((x + 1 - p1.x) * (p2.y - p1.y), p2.x - p1.x);
segs[x].push_back(seg(l, r));
}
}
frac get(frac l, frac r, frac y) {
if (l < y && r < y) return frac(0, 1);
if (!(l < y) && !(r < y)) return (l + r) / frac(2, 1) - y;
if (r < l) swap(l, r);
return (r - y) * (r - y) / (r - l) / frac(2, 1);
}
frac calc(int x, int y) { // higher than y
if (segs[x].size() == 0) return frac(0, 1);
assert(segs[x].size() == 2);
return get(segs[x][1].l, segs[x][1].r, frac(y, 1)) -
get(segs[x][0].l, segs[x][0].r, frac(y, 1));
}
frac solve(point b) {
return (calc(b.x - 1, b.y - 1) - calc(b.x - 1, b.y + 1) +
calc(b.x, b.y - 1) - calc(b.x, b.y + 1)) /
frac(4, 1);
}
int main() {
scanf("%d%d", &n, &q);
rep(i, 0, n - 1) { a[i].read(); }
a[n] = a[0];
rep(i, 0, n - 1) { put(a[i], a[i + 1]); }
rep(i, 0, 2001) {
if (segs[i].size()) {
sort(segs[i].begin(), segs[i].end());
// printf("%d:\n", i);
// for (auto s : segs[i]) {
// s.print();
// }
}
}
rep(i, 0, q - 1) {
point b;
b.read();
solve(b).print();
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3832kb
input:
4 4 1 1 4 1 4 4 1 4 3 3 10 10 1 3 1 4
output:
1/1 0/1 1/2 1/4
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
3 4 1 1 11 11 1 21 1 1 11 11 21 1 4 4
output:
1/8 1/4 0/1 1/2
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
4 6 10 10 11 10 11 11 10 11 10 10 11 10 11 11 10 11 9 10 11 12
output:
1/4 1/4 1/4 1/4 0/1 0/1
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 4012kb
input:
4 999 0 0 1000 0 1000 1000 0 1000 0 0 1000 0 1000 1000 0 1000 483 55 841 0 116 1000 0 212 1000 809 43 400 439 0 769 1000 0 106 1000 175 419 275 755 0 565 1000 0 531 1000 959 11 736 982 0 254 1000 0 965 1000 975 208 472 164 0 732 1000 0 133 1000 18 780 203 977 0 223 1000 0 772 1000 227 398 600 729 0 ...
output:
1/4 1/4 1/4 1/4 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 1/2 1/2 1/2 1/2 1/1 ...
result:
ok 999 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
3 993 0 0 1000 500 0 1000 0 0 1000 500 0 1000 11 383 0 954 806 403 806 404 806 402 636 628 0 826 880 440 880 441 880 439 701 686 0 957 250 125 250 126 250 124 137 469 0 341 180 90 180 91 180 89 638 267 0 495 770 385 770 386 770 384 723 110 0 577 46 23 46 24 46 22 250 56 0 224 446 223 446 224 446 222...
output:
3/16 1/8 3/16 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 1/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 0/1 1/2 1/2 1/1 0/1 1/1 1/...
result:
ok 993 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 3844kb
input:
4 64 1 1 5 2 5 5 1 6 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 6 0 6 1 6 2 6 3 6 4 6 5 6 6 6 7 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7
output:
0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 7/32 1/2 1/2 1/2 1/2 7/32 0/1 0/1 1/4 1/1 1/1 1/1 1/1 1/4 0/1 0/1 1/32 31/32 1/1 1/1 31/32 1/32 0/1 0/1 0/1 3/4 1/1 1/1 3/4 0/1 0/1 0/1 0/1 9/32 1/2 1/2 9/32 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1
result:
ok 64 lines
Test #7:
score: 0
Accepted
time: 6ms
memory: 4084kb
input:
100 999 0 0 1000 500 998 501 996 502 994 503 992 504 990 505 988 506 986 507 984 508 982 509 980 510 978 511 976 512 974 513 972 514 970 515 968 516 966 517 964 518 962 519 960 520 958 521 956 522 954 523 952 524 950 525 948 526 946 527 944 528 942 529 940 530 938 531 936 532 934 533 932 534 930 535...
output:
3/16 1/8 3/16 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 1/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/2 0/1 1/2 1/...
result:
ok 999 lines
Test #8:
score: -100
Wrong Answer
time: 5ms
memory: 4088kb
input:
10 1000 1000 83 993 569 990 675 976 958 969 982 870 993 374 999 1 1000 0 0 482 0 1000 83 993 569 990 675 976 958 969 982 870 993 374 999 1 1000 0 0 482 0 102 800 569 366 623 371 296 429 735 83 872 500 61 864 611 578 184 642 210 796 302 16 723 865 227 354 290 167 970 724 757 902 227 858 13 681 900 74...
output:
33763/125874 51337/103032 119357/239984 25523/54336 173/576 8707/17856 369145/740032 745373/2984000 -1999/8000 1989/4144 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1...
result:
wrong answer 9th lines differ - expected: '1999/8000', found: '-1999/8000'