QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23806#2959. AntialiasingGeorge_Plover#WA 7ms4088kbC++202.9kb2022-03-19 15:27:062022-04-30 04:10:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:10:06]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:4088kb
  • [2022-03-19 15:27:06]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'