QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23814#2959. AntialiasingGeorge_Plover#AC ✓15ms4088kbC++203.0kb2022-03-19 16:03:102022-04-30 04:10:58

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:58]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:4088kb
  • [2022-03-19 16:03:10]
  • 提交

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 > 0);
    }
    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; }
    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 ? r < rhs.r : 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) {
    if (l < frac(0, 1) && r < frac(0, 1)) return frac(0, 1);
    if (!(l < frac(0, 1)) && !(r < frac(0, 1))) return (l + r) / frac(2, 1);
    if (r < l) swap(l, r);
    return r * r / (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 - frac(y, 1), segs[x][1].r - frac(y, 1)) -
           get(segs[x][0].l - frac(y, 1), 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: 1ms
memory: 3908kb

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: 1ms
memory: 3824kb

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: 3848kb

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: 5ms
memory: 4032kb

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: 6ms
memory: 4028kb

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: 3852kb

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: 3ms
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: 0
Accepted
time: 9ms
memory: 4012kb

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:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 4ms
memory: 4036kb

input:

10 1000
1000 164
999 446
996 653
985 898
966 962
910 984
619 999
381 999
162 998
69 993
1000 164
999 446
996 653
985 898
966 962
910 984
619 999
381 999
162 998
69 993
671 117
755 386
177 56
262 542
35 802
772 415
970 45
338 947
933 571
496 412
652 567
937 433
910 789
964 657
68 253
85 686
941 566
2...

output:

290375/2100336
25873/51888
33553/67620
58769/125440
1205/3584
9937/21728
383/776
875/1752
13411/27156
10219/86583
0/1
1/1
0/1
0/1
0/1
1/1
0/1
1/1
1/1
0/1
1/1
1/1
1/1
1/1
0/1
0/1
1/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
1/1
0/1
0/1
1/1
0/1
0/1
0/1
0/1
1/1
1/1
1/1
0/1
0/1
0/1
0/1
1/1
0/1
0/1
1/1
0/1
0/1
1/...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 9ms
memory: 4000kb

input:

20 1000
1000 514
1000 723
998 879
987 971
922 984
723 992
191 1000
13 986
6 962
0 621
0 541
1 73
13 20
304 2
547 1
737 7
954 27
976 90
986 139
996 223
1000 514
1000 723
998 879
987 971
922 984
723 992
191 1000
13 986
6 962
0 621
0 541
1 73
13 20
304 2
547 1
737 7
954 27
976 90
986 139
996 223
529 75...

output:

145/291
311/624
13969/28704
1067/3680
3821/7960
52601/105868
46239/94696
5063/17088
30493/65472
679/1364
1871/3744
93653/198432
2941/10282
92923/188568
22879/46170
81211/164920
596/1953
425/882
1151/2352
5289/10864
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...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 3ms
memory: 4024kb

input:

20 1000
999 315
998 998
891 999
556 999
439 999
196 999
148 994
1 946
0 621
0 313
1 244
5 102
9 55
48 22
53 21
473 1
949 0
980 13
995 127
997 144
999 315
998 998
891 999
556 999
439 999
196 999
148 994
1 946
0 621
0 313
1 244
5 102
9 55
48 22
53 21
473 1
949 0
980 13
995 127
997 144
160 321
548 651
...

output:

465635/934344
18369/73081
427/856
1/2
1/2
187/384
8885/18816
37099/127400
1299/2600
275/552
19529/39192
6579/13348
1791/4888
109/260
101/210
5647/11424
52805/118048
3005/9424
2575/5168
1415/2907
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
3/68
1/1
1/2
1/1
1/1
1/1
1/1
1/1
1/1
1/1
1/1
1/1
1/1
...

result:

ok 1000 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 4016kb

input:

19 1000
1000 29
996 627
988 850
977 968
946 996
710 1000
455 998
107 990
30 968
12 933
2 848
0 621
1 81
16 44
69 0
481 1
859 8
902 12
982 23
1000 29
996 627
988 850
977 968
946 996
710 1000
455 998
107 990
30 968
12 933
2 848
0 621
1 81
16 44
69 0
481 1
859 8
902 12
982 23
660 506
908 699
737 861
56...

output:

2087/7176
132381/266708
103747/210512
10961/29264
5695/14632
59807/120360
7367/14790
569/1218
7/20
268/595
1877/3859
489013/980640
71857/159840
6345/15688
69163/174688
44317/88992
9115/18576
13607/27520
913/1920
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
...

result:

ok 1000 lines

Test #13:

score: 0
Accepted
time: 9ms
memory: 3996kb

input:

20 1000
1000 162
1000 626
997 906
995 965
955 980
833 999
616 1000
24 992
15 976
4 944
3 901
0 621
12 161
18 64
105 13
156 7
396 1
929 3
982 23
997 48
1000 162
1000 626
997 906
995 965
955 980
833 999
616 1000
24 992
15 976
4 944
3 901
0 621
12 161
18 64
105 13
156 7
396 1
929 3
982 23
997 48
776 85...

output:

151/304
1117/2240
65697/132160
1137/3776
1845/3904
101895/211792
63941/128464
1525/4736
121/256
5063/11008
48009/96320
25523/51520
44221/89240
7449/22504
1741/3944
2657/5440
84667/170560
51221/112996
789/2120
651/1520
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/...

result:

ok 1000 lines

Test #14:

score: 0
Accepted
time: 3ms
memory: 4016kb

input:

22 1000
1000 565
999 953
941 993
867 999
516 1000
201 1000
179 1000
58 999
39 989
19 968
12 949
0 621
1 117
5 64
26 27
56 8
130 0
698 0
835 0
924 2
989 25
997 48
1000 565
999 953
941 993
867 999
516 1000
201 1000
179 1000
58 999
39 989
19 968
12 949
0 621
1 117
5 64
26 27
56 8
130 0
698 0
835 0
924 ...

output:

800703/1604768
30293/90016
3639/8584
12733/25974
1403/2808
1/2
483/968
8005/18392
347/798
1363/3192
5715/12464
81859/165312
104885/213696
6879/15688
3553/8880
3857/8880
18/37
1/2
177/356
21223/46280
4039/11960
43497/95128
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/...

result:

ok 1000 lines

Test #15:

score: 0
Accepted
time: 9ms
memory: 4016kb

input:

21 1000
1000 505
1000 933
962 971
865 997
529 1000
235 1000
123 1000
49 983
10 923
3 756
0 621
0 259
6 178
7 167
17 104
30 56
74 12
179 4
368 0
881 1
997 48
1000 505
1000 933
962 971
865 997
529 1000
235 1000
123 1000
49 983
10 923
3 756
0 621
0 259
6 178
7 167
17 104
30 56
74 12
179 4
368 0
881 1
9...

output:

1825/3656
3/8
317/776
40641/86912
447/896
1/2
279/592
2131/5920
11329/26720
3739/7515
179/360
53/108
1183/2376
2725/5544
3919/8064
157/384
323/840
466/945
14281/28728
214037/476064
127851/424096
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...

result:

ok 1000 lines

Test #16:

score: 0
Accepted
time: 11ms
memory: 3952kb

input:

21 1000
997 48
997 932
997 983
976 991
886 995
768 996
479 997
365 996
279 995
53 992
20 985
0 923
0 740
0 621
0 586
1 164
2 11
205 1
943 2
968 15
973 18
997 48
997 932
997 983
976 991
886 995
768 996
479 997
365 996
279 995
53 992
20 985
0 923
0 740
0 621
0 586
1 164
2 11
205 1
943 2
968 15
973 18
...

output:

2/5
1/2
25/84
577/1260
21049/42480
136237/272816
131381/263568
9797/19608
4857/9718
28349/59664
2593/8184
57/124
1/2
1/2
1687/3376
257995/516528
63851/248472
591673/1198512
64231/147600
49/100
17/40
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
1/1
0/1
1/1
1/1
1/1
1/1
1...

result:

ok 1000 lines

Test #17:

score: 0
Accepted
time: 8ms
memory: 4028kb

input:

18 1000
999 156
998 597
996 850
995 921
990 989
733 1000
528 1000
29 998
13 970
0 923
0 242
10 42
28 24
113 0
887 0
951 1
973 18
987 33
999 156
998 597
996 850
995 921
990 989
733 1000
528 1000
29 998
13 970
0 923
0 242
10 42
28 24
113 0
887 0
951 1
973 18
987 33
965 725
937 282
361 660
364 285
300 ...

output:

70519/144648
445663/892584
71741/143704
19025/38624
36985/139808
1017/2056
997/1996
2249/6986
1219/2632
175/376
79/160
61/160
279/680
79/170
255/512
2283/5632
1223/2640
973/2460
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
1/1
1/1
1/1
1/...

result:

ok 1000 lines

Test #18:

score: 0
Accepted
time: 9ms
memory: 4088kb

input:

17 1000
999 983
906 988
752 993
62 999
23 990
1 930
0 923
5 4
661 1
793 1
951 1
973 18
987 33
995 176
996 198
997 273
998 589
999 983
906 988
752 993
62 999
23 990
1 930
0 923
5 4
661 1
793 1
951 1
973 18
987 33
995 176
996 198
997 273
998 589
754 407
483 911
905 23
346 118
895 457
883 331
804 218
2...

output:

75161/293136
56983/114576
70419/141680
2811/5980
1013/3120
793/1680
12389/25732
1211765/4822912
2621/5248
1/2
71/176
1223/2640
3349/8580
1141/2288
6547/13200
94559/189600
248969/498016
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
1/1
1/1...

result:

ok 1000 lines

Test #19:

score: 0
Accepted
time: 7ms
memory: 4032kb

input:

16 1000
998 297
998 397
998 589
996 954
995 961
952 992
946 996
51 1000
0 923
0 164
1 71
12 15
113 2
570 0
992 3
996 198
998 297
998 397
998 589
996 954
995 961
952 992
946 996
51 1000
0 923
0 164
1 71
12 15
113 2
570 0
992 3
996 198
126 205
131 699
431 702
66 119
691 701
587 518
921 95
381 549
856 ...

output:

197/396
1/2
729/1460
9869/20440
431/1204
509/1032
4481/10740
183167/551320
257/616
371/744
19865/41664
13151/45248
178889/369256
769201/1542832
166853/658320
12869/25740
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
1/1
0/1
1/1
1/1
1/1
1/...

result:

ok 1000 lines

Test #20:

score: 0
Accepted
time: 6ms
memory: 4016kb

input:

16 1000
1000 480
1000 823
999 995
712 1000
535 1000
85 996
28 995
0 923
0 426
3 59
18 22
51 10
83 5
120 2
992 3
999 88
1000 480
1000 823
999 995
712 1000
535 1000
85 996
28 995
0 923
0 426
3 59
18 22
51 10
83 5
120 2
992 3
999 88
440 880
481 982
486 601
579 571
288 496
433 66
911 661
897 126
782 945...

output:

1567/3136
687/1376
99875/394912
1143/2296
449/900
17063/34200
823/2736
65/144
1465/2936
24461/54316
1127/3256
1335/2816
4647/9472
126403/258112
154429/592960
130621/266560
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
1/1
1/1
1/1
1/1
1/1
...

result:

ok 1000 lines

Test #21:

score: 0
Accepted
time: 8ms
memory: 4088kb

input:

18 1000
1000 619
1000 835
992 939
988 984
831 999
500 999
446 999
347 999
3 996
0 923
0 918
0 700
4 23
74 5
372 0
569 0
992 3
999 88
1000 619
1000 835
992 939
988 984
831 999
500 999
446 999
347 999
3 996
0 923
0 918
0 700
4 23
74 5
372 0
569 0
992 3
999 88
971 323
816 624
912 785
970 83
344 809
420...

output:

2123/4248
51/104
2333/4680
15433/56520
613/1256
1/2
1/2
1373/2752
51475/200896
289/584
1/2
338/677
53623/189560
39213/83440
1187/2384
563/1128
12521/47940
44227/90270
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
1/1
1/1
1/1
1/1
1/2
1/1
1...

result:

ok 1000 lines

Test #22:

score: 0
Accepted
time: 2ms
memory: 4000kb

input:

18 1000
999 88
999 220
999 415
998 999
640 1000
616 1000
575 1000
315 1000
112 1000
19 966
0 923
5 184
8 102
26 10
161 4
282 3
834 0
986 1
999 88
999 220
999 415
998 999
640 1000
616 1000
575 1000
315 1000
112 1000
19 966
0 923
5 184
8 102
26 10
161 4
282 3
834 0
986 1
153 524
467 111
34 748
632 878...

output:

335/696
1/2
2335/4672
209543/836288
1431/2864
1/2
1/2
1/2
169/372
11227/31992
28213/63554
240585/484784
1811/3772
4637/16560
21583/43560
88993/178112
6971/13984
28511/105792
1/1
1/1
1/1
1/1
1/1
1/1
1/1
1/1
0/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
1/1
1/1
1/1
1/...

result:

ok 1000 lines

Test #23:

score: 0
Accepted
time: 10ms
memory: 4024kb

input:

18 1000
999 220
998 298
984 981
979 995
788 1000
119 999
69 997
0 923
0 802
0 630
0 521
0 111
6 21
41 5
385 0
834 0
986 1
991 46
999 220
998 298
984 981
979 995
788 1000
119 999
69 997
0 923
0 802
0 630
0 521
0 111
6 21
41 5
385 0
834 0
986 1
991 46
147 414
791 333
495 898
503 777
860 97
366 909
430...

output:

8915/18096
212687/426192
35029/76496
6373/21392
126895/255558
8282/16725
5499/14800
227/592
1/2
1/2
1/2
59/120
53/168
42831/96320
1371/2752
607/1216
2897/10944
1027/2088
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
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:

ok 1000 lines

Test #24:

score: 0
Accepted
time: 6ms
memory: 3952kb

input:

16 1000
1000 31
1000 413
997 972
992 977
951 985
887 994
130 1000
82 996
13 975
0 923
0 741
0 233
1 64
13 5
824 0
986 1
1000 31
1000 413
997 972
992 977
951 985
887 994
130 1000
82 996
13 975
0 923
0 741
0 233
1 64
13 5
824 0
986 1
228 130
424 658
960 693
636 768
696 706
711 209
119 240
178 639
797 ...

output:

53/120
2233/4472
210/559
131/328
10353/20992
187363/387584
35507/72672
1043/2208
235/736
15/32
1/2
675/1352
37915/79768
105725/382792
523907/1051056
2003/6480
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
1/1
0/1
1/1
1/1
1/1
1/1
1/1
1/1
1...

result:

ok 1000 lines

Test #25:

score: 0
Accepted
time: 11ms
memory: 4048kb

input:

19 1000
1000 588
1000 825
989 964
988 976
987 985
967 996
811 999
126 998
15 993
0 984
0 923
4 103
12 24
18 10
143 3
351 1
824 0
986 1
998 17
1000 588
1000 825
989 964
988 976
987 985
967 996
811 999
126 998
15 993
0 984
0 923
4 103
12 24
18 10
143 3
351 1
824 0
986 1
998 17
820 266
461 326
244 895
...

output:

1141/2284
545/1112
6665/13344
143/288
479/1440
451/1040
141743/284960
150413/304140
239/555
13/40
819/1640
63219/129560
2031/4424
1087/3500
51397/104000
196399/393536
305869/613008
893/2592
7431/18272
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...

result:

ok 1000 lines

Test #26:

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

input:

13 1000
1000 235
996 965
885 988
645 997
303 1000
86 998
0 984
2 13
69 5
401 0
840 2
966 4
998 17
1000 235
996 965
885 988
645 997
303 1000
86 998
0 984
2 13
69 5
401 0
840 2
966 4
998 17
977 287
558 841
999 41
184 55
756 273
831 328
750 878
184 499
261 200
466 897
977 592
508 962
994 114
233 779
38...

output:

158557/318280
89647/324120
34013/71040
18109/36480
98507/197904
35891/74648
90217/334024
17252/65057
86655/177952
580133/1165984
110315/221256
7277/16128
8425/27904
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
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:

ok 1000 lines

Test #27:

score: 0
Accepted
time: 7ms
memory: 4004kb

input:

15 1000
1000 35
1000 558
997 946
867 978
855 980
728 1000
170 1000
38 992
0 984
1 417
4 363
30 25
66 1
966 4
999 13
1000 35
1000 558
997 946
867 978
855 980
728 1000
170 1000
38 992
0 984
1 417
4 363
30 25
66 1
966 4
999 13
918 161
109 193
431 411
8 131
383 116
295 157
46 863
114 245
877 461
182 79
...

output:

87/176
1549/3104
56843/201760
1529/3120
3041/6096
61/127
65/132
1207/2508
23795/86184
4475/9072
931/1872
107/312
333/800
12311/26400
51/176
1/1
1/1
1/1
0/1
1/1
1/1
1/1
1/1
1/1
1/1
1/1
0/1
1/1
0/1
1/1
1/1
1/1
1/1
1/1
1/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:

ok 1000 lines

Test #28:

score: 0
Accepted
time: 3ms
memory: 3816kb

input:

4 4
3 0
5 4
3 8
1 4
3 0
5 4
3 8
1 4

output:

1/8
3/8
1/8
3/8

result:

ok 4 lines

Test #29:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

4 4
0 2
4 0
8 2
4 4
0 2
4 0
8 2
4 4

output:

1/8
3/8
1/8
3/8

result:

ok 4 lines