QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#23806 | #2959. Antialiasing | George_Plover# | WA | 7ms | 4088kb | C++20 | 2.9kb | 2022-03-19 15:27:06 | 2022-04-30 04:10:06 |
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;
}
}
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("%d/%d", 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) / (l + r - y - y) / 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) {
sort(segs[i].begin(), segs[i].end());
// if (segs[i].size()) {
// 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
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: 3ms
memory: 3820kb
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: 3ms
memory: 3744kb
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: 0ms
memory: 4088kb
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: 7ms
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: 3840kb
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: 5ms
memory: 3996kb
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: 3928kb
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:
17775/977984 23071/94400 9767/40800 127/816 127/720 8707/17856 369145/740032 743137/2978032 1/7984 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 1/1 1/1 1/1...
result:
wrong answer 1st lines differ - expected: '33763/125874', found: '17775/977984'