QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#456419#7131. Random pointspropaneAC ✓322ms4052kbC++203.2kb2024-06-27 21:56:142024-06-27 21:56:14

Judging History

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

  • [2024-06-27 21:56:14]
  • 评测
  • 测评结果:AC
  • 用时:322ms
  • 内存:4052kb
  • [2024-06-27 21:56:14]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 2005, mod = 1e9 + 7;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

int sub(int a, int b){
    a -= b;
    if (a < 0) a += mod;
    return a;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int pow2[maxn];

struct Point{
    LL x, y;

    bool operator==(const Point &t) const {
        return x == t.x and y == t.y;
    }

    Point operator-(const Point &t) const {
        return {x - t.x, y - t.y};
    }

    LL operator*(const Point &t) const {
        return x * t.x + y * t.y;
    }

    LL operator^(const Point &t) const {
        return x * t.y - y * t.x;
    }

    int quad() const {
        if (y < 0) return 1;
        if (y > 0) return 4;
        if (x > 0) return 2;
        if (x < 0) return 5;
        return 3;
    }

    bool operator<(const Point &t) const {
        int q1 = quad(), q2 = t.quad();
        if (q1 != q2) return q1 < q2;
        LL cross = (*this ^ t);
        if (cross != 0) return cross > 0;
        return (*this) * (*this) < t * t;
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    pow2[0] = 1;
    for(int i = 1; i < maxn; i++){
        pow2[i] = mul(pow2[i - 1], 2);
    }

    int n;
    cin >> n;
    vector<Point> p(n);
    map<Point, int> mp;
    for(int i = 0; i < n; i++){
        cin >> p[i].x >> p[i].y;
        mp[p[i]] += 1;
    }
    int ans = 0;

    // 枚举每个点,计算其出现在凸包上的方案数
    // 对于剩下的点极角排序后如果选择的其余点都在一个半平面,则该点在凸包上.
    // 否则肯定被包含
    // 枚举点集的方法,枚举极角序最小的点是哪个,然后找到所有与其夹角不超过pi的点
    // 边界问题,极角序可能相同,一起枚举可以避免双指针转圈转回去
    for(auto &[u, cnt] : mp){
        vector<Point> q;
        q.reserve(p.size());
        for(auto pt : p){
            if (pt != u){
                q.push_back(pt - u);
            }
        }
        sort(q.begin(), q.end());

        auto check1 = [&](int x, int y){
            LL t = q[x] ^ q[y];
            if (t > 0) return true;
            if (t < 0) return false;
            return (q[x] * q[y]) > 0;
        };
        
        auto check2 = [&](int x, int y){
            LL t = q[x] ^ q[y];
            LL s = q[x] * q[y];
            return t == 0 and s > 0;
        };

        const int m = q.size();
        q.resize(2 * m);
        for(int i = 0; i < m; i++) q[i + m] = q[i];

        // 空集也是可以的
        int sum = 1;
        for(int i = 0, j = 0, k = 0; i < m; i = j){
            while(j < m + i and check2(i, j)) j++;
            k = max(k, j);
            while(k < m + i and check1(i, k)) k++;
            int c1 = j - i;
            int c2 = k - j;
            add(sum, mul(sub(pow2[c1], 1), pow2[c2]));
        }
        add(ans, mul(sub(pow2[cnt], 1), sum));
    }
    cout << ans << '\n';

}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

input:

3
0 0
0 1
1 0

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

3
0 0
0 1
0 2

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

20
3 3
1 0
0 2
2 2
2 4
4 3
0 0
1 4
0 1
4 2
3 4
1 0
3 1
4 4
3 1
1 3
4 1
1 4
3 0
3 1

output:

5996938

result:

ok 1 number(s): "5996938"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

20
3 1
2 2
3 3
3 3
3 4
1 0
4 0
2 1
4 2
0 2
2 3
4 2
4 0
4 0
4 1
0 3
3 3
3 4
0 4
2 1

output:

5252571

result:

ok 1 number(s): "5252571"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

20
1 2
0 1
1 2
1 4
3 3
0 0
0 4
1 3
1 2
0 2
1 0
0 2
0 2
1 0
1 4
2 4
2 0
3 1
1 1
0 2

output:

5321297

result:

ok 1 number(s): "5321297"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

20
0 0
2 0
3 3
0 1
1 4
0 3
0 0
4 0
4 4
1 3
1 1
3 3
2 3
4 1
4 4
3 1
1 4
0 4
1 3
4 3

output:

4876981

result:

ok 1 number(s): "4876981"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

20
1 1
0 3
0 1
0 1
2 2
3 1
0 3
3 2
4 1
2 2
4 3
0 1
3 0
3 1
0 2
3 4
4 1
3 0
4 3
0 0

output:

5073888

result:

ok 1 number(s): "5073888"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

20
3 4
4 0
4 3
3 2
3 3
3 0
1 4
3 1
0 4
2 4
3 4
2 0
0 4
0 3
4 4
0 1
2 0
1 1
3 4
1 1

output:

5516468

result:

ok 1 number(s): "5516468"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

20
3 2
4 4
0 4
4 4
3 3
4 3
3 2
4 3
4 0
1 4
3 0
4 3
1 0
3 4
1 2
1 4
4 3
1 2
1 0
2 2

output:

4561298

result:

ok 1 number(s): "4561298"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

20
0 1
2 2
1 2
2 0
1 2
3 0
4 2
2 1
1 0
2 0
2 2
2 4
2 2
1 0
3 1
3 1
4 4
3 0
2 1
1 3

output:

5273582

result:

ok 1 number(s): "5273582"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

20
0 4
4 1
4 4
2 1
3 3
2 0
4 1
3 2
3 2
2 0
2 4
0 0
2 1
0 1
0 0
2 3
2 2
2 0
2 3
4 4

output:

4934815

result:

ok 1 number(s): "4934815"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

20
0 1
2 4
3 2
1 3
4 3
4 0
4 4
3 4
4 3
0 4
0 0
4 2
4 3
2 1
4 4
0 0
2 1
2 4
0 1
0 0

output:

5033049

result:

ok 1 number(s): "5033049"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

20
19 19
1 1
4 5
10 20
3 4
11 19
20 15
6 0
9 17
17 16
8 18
18 16
0 16
15 6
8 10
1 7
11 18
5 2
10 19
4 13

output:

6215411

result:

ok 1 number(s): "6215411"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

20
5 2
3 8
18 13
20 9
11 18
7 4
3 6
8 16
8 0
18 16
0 14
7 8
9 3
12 1
17 8
17 20
7 19
5 14
1 11
6 0

output:

7150834

result:

ok 1 number(s): "7150834"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

20
5 7
1 18
19 13
10 3
18 12
17 1
20 14
9 3
7 9
6 7
16 1
12 8
14 15
10 12
13 11
3 17
9 0
12 1
14 16
2 11

output:

5655954

result:

ok 1 number(s): "5655954"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

20
5 4
10 17
4 17
16 0
5 14
17 7
7 5
19 19
2 1
3 20
15 5
17 5
19 6
11 2
9 1
5 9
19 5
4 9
5 13
8 15

output:

5525854

result:

ok 1 number(s): "5525854"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

20
4 4
16 7
2 0
6 10
9 11
9 5
20 9
20 5
1 10
3 3
7 13
18 1
7 1
0 13
18 20
20 5
12 19
12 9
18 13
18 1

output:

5996819

result:

ok 1 number(s): "5996819"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

20
12 9
4 14
16 17
12 3
16 5
18 7
7 0
9 0
13 18
17 12
15 18
2 5
12 13
6 4
15 2
10 19
1 7
12 16
9 10
3 13

output:

7358820

result:

ok 1 number(s): "7358820"

Test #19:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

20
12 9
6 9
9 0
19 1
3 3
11 4
20 12
10 7
12 10
17 3
6 18
7 18
18 4
20 19
11 17
12 19
10 0
11 7
18 3
8 20

output:

6109530

result:

ok 1 number(s): "6109530"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

20
15 14
7 19
20 4
8 11
6 13
3 10
7 3
12 7
11 19
18 16
6 1
8 15
2 16
17 9
20 20
2 12
20 9
19 15
10 7
1 3

output:

5983987

result:

ok 1 number(s): "5983987"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

20
2 7
17 5
17 8
18 4
5 19
12 8
7 11
0 10
6 3
14 16
1 9
9 19
7 11
15 8
16 14
13 8
9 7
19 6
5 0
7 18

output:

6056527

result:

ok 1 number(s): "6056527"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

20
4 4
8 15
11 12
13 8
4 7
19 10
15 13
5 11
12 2
8 9
14 6
10 11
1 0
18 9
2 11
10 1
11 15
20 4
0 20
18 20

output:

5673043

result:

ok 1 number(s): "5673043"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

20
336405873 965255840
652652222 713068201
61495714 864495608
289278684 273789489
705069803 645861692
283828514 807458721
135671792 915838066
347383048 781174151
27017020 165786268
525637386 825246400
999273165 170356496
298705494 542641581
341157969 620048533
800792019 74468194
984766973 453177943
...

output:

6305503

result:

ok 1 number(s): "6305503"

Test #24:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

20
252299584 188575412
500890006 956938247
568072747 568848227
587114620 755768888
617427087 934427639
834979913 346516263
3441700 707340534
135002005 965711294
928983573 745563964
871761848 196491818
592549325 478511618
41256982 558819978
127405696 280355780
77055590 900799165
767802897 415054489
4...

output:

7583216

result:

ok 1 number(s): "7583216"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

20
94564367 821960402
54160499 495775584
369617070 346829774
884950557 164119358
571253568 222993586
722567801 549137317
871211609 130246782
554024742 518844655
535982833 30374368
627951726 862704529
890858194 155262959
447371983 206402156
618686132 14291956
648286454 432162842
919435041 155592671
4...

output:

6113607

result:

ok 1 number(s): "6113607"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

20
305425371 45279974
533802064 444678338
171161394 419778612
887819201 646098758
483610852 511559533
610155688 383162151
444014225 626781959
678080188 71978017
364320458 315184772
974076188 528917239
189167063 463418081
894956180 222580553
478562787 84664620
219517317 553461104
407503672 117469217
...

output:

6764925

result:

ok 1 number(s): "6764925"

Test #27:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

20
147690154 973632256
87072557 688548385
972705718 902792868
112026208 54449228
732404625 168721699
161307087 585783206
680380353 123317134
97102924 256515160
266287010 894962468
320200649 531566439
487475932 771573203
6103888 533726242
674875931 113568087
127184669 84824781
895572305 784378472
485...

output:

6070154

result:

ok 1 number(s): "6070154"

Test #28:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

20
63583865 607017245
935310342 932418431
774250042 975741707
114894853 536428627
981198398 162320354
343862266 124840748
253182969 251256091
884721882 809648523
168253562 548369091
371357819 902811858
785784801 153357252
43622668 549904640
461123658 478908044
403448241 911155751
342171740 819883946...

output:

7110644

result:

ok 1 number(s): "7110644"

Test #29:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

20
200815941 830336818
783548127 176288476
280827074 385127033
412730789 313375317
598588390 450886301
895013666 327461802
825985586 42758559
303744618 362781884
70220114 128146787
717482281 569024568
84093669 756479666
154770376 566083037
321000313 212844219
679711814 442519429
830240373 486793201
...

output:

6109083

result:

ok 1 number(s): "6109083"

Test #30:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

20
748113433 463721807
336818619 420158523
82371397 458075872
710566725 426758497
847382163 739452248
782601553 866519345
693755494 539293736
427800064 547319027
603590448 412957191
63606742 866641059
677369830 769667496
897321866 582261434
812280750 578184176
882346458 268850398
613276296 522298675...

output:

5471625

result:

ok 1 number(s): "5471625"

Test #31:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

20
958974436 392074088
185056404 664028569
515319502 236057419
713435369 908737896
464772155 28018194
38785660 69140399
266558111 962199984
215419021 100452389
800524292 992734887
114763912 532853770
975678699 446418837
8469573 893407123
303561185 312120351
453577321 800214076
101344928 189207929
21...

output:

6290548

result:

ok 1 number(s): "6290548"

Test #32:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

20
839459118 250813388
210886587 446341423
734699739 162312946
524969959 813259360
258532670 119007402
923976993 893230085
550966829 448774111
741957996 712341646
706719531 570008421
787701275 362968182
522566755 949914939
38822846 811020160
966058391 438380044
477726558 572987885
123261355 68952904...

output:

5963046

result:

ok 1 number(s): "5963046"

Test #33:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

100
17 6
15 13
3 13
15 2
3 17
4 0
7 11
20 13
7 18
14 4
13 20
15 18
6 4
8 12
2 17
8 6
15 7
17 0
13 10
18 19
20 9
3 18
14 7
13 1
15 8
10 11
8 16
20 9
8 5
4 9
6 7
8 19
12 1
7 2
7 7
4 16
1 19
5 4
9 19
14 11
7 15
2 20
17 6
1 11
5 16
17 4
14 20
7 14
2 18
14 0
19 12
0 13
16 5
16 1
0 8
12 16
1 10
4 11
18 1
...

output:

629516671

result:

ok 1 number(s): "629516671"

Test #34:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

100
10 11
17 7
2 10
20 2
10 14
5 17
12 17
17 6
8 20
5 9
14 15
20 8
10 7
11 9
4 2
9 3
15 8
15 10
9 14
15 18
2 2
14 15
10 20
9 10
10 18
14 12
15 17
11 15
13 13
3 16
11 3
10 13
2 7
2 8
15 13
8 0
9 0
12 0
14 7
20 15
8 7
2 7
1 3
18 17
18 10
10 19
4 3
0 5
8 15
19 9
11 11
10 13
17 4
5 0
2 11
12 8
6 10
10 3...

output:

772969884

result:

ok 1 number(s): "772969884"

Test #35:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100
7 2
15 13
6 14
5 16
17 14
2 13
0 15
10 11
1 14
18 11
11 14
16 18
20 15
15 7
9 11
14 4
2 2
6 4
12 6
17 14
17 12
4 8
18 12
1 6
1 14
5 1
10 10
7 12
15 17
19 14
16 7
0 11
17 17
15 14
2 11
7 5
1 20
11 0
16 12
2 18
0 15
18 6
2 10
7 14
5 16
12 3
8 3
15 17
19 11
17 5
3 10
20 17
18 8
19 11
9 14
9 13
18 9...

output:

547585677

result:

ok 1 number(s): "547585677"

Test #36:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

100
8 7
16 3
2 18
14 12
20 10
3 13
0 20
12 3
6 16
18 16
16 17
9 4
16 19
5 4
11 8
7 5
2 4
14 10
7 7
6 10
17 1
16 1
14 16
18 19
3 7
9 19
17 11
6 18
16 12
14 20
8 4
6 13
8 14
10 3
14 13
2 10
18 14
11 13
17 0
5 14
14 3
0 10
8 4
3 19
4 0
4 4
2 16
8 20
4 7
18 0
16 17
0 17
2 20
9 5
7 8
9 9
10 9
0 8
9 9
15 ...

output:

145089569

result:

ok 1 number(s): "145089569"

Test #37:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

100
19 19
14 18
1 15
2 16
6 11
8 9
9 1
6 4
7 18
6 4
13 15
5 19
17 14
17 1
16 14
12 1
20 19
8 20
7 7
7 9
20 15
6 15
5 8
10 19
19 4
0 17
11 16
2 16
17 12
13 18
9 17
12 6
15 0
2 9
1 16
19 10
13 17
18 13
19 9
8 1
10 15
17 10
0 10
0 8
12 10
18 13
9 3
2 7
7 8
2 0
15 16
14 0
3 11
19 16
18 8
14 6
19 4
10 4
...

output:

356436740

result:

ok 1 number(s): "356436740"

Test #38:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100
20 6
8 16
18 19
12 8
1 11
1 18
14 3
16 18
8 20
1 10
18 1
10 9
9 6
7 16
18 2
5 2
3 20
20 14
19 3
9 9
14 7
17 8
14 7
6 7
14 14
4 1
18 9
14 0
2 7
4 16
14 0
1 4
9 18
14 14
14 10
1 15
18 7
0 9
7 15
10 4
15 11
20 17
5 17
17 5
3 3
7 7
4 3
16 1
17 8
4 16
7 16
3 0
20 2
9 15
20 11
14 19
11 4
12 20
9 19
16...

output:

210583523

result:

ok 1 number(s): "210583523"

Test #39:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

100
0 19
6 10
1 15
9 1
8 3
6 18
1 4
13 18
10 5
10 2
2 17
19 20
2 5
11 13
2 16
10 15
20 14
19 3
2 8
6 4
18 17
11 18
9 20
19 8
4 14
20 20
12 7
10 2
7 7
3 6
15 17
8 2
4 3
6 3
5 12
0 20
13 10
20 17
9 3
13 0
7 20
19 13
11 11
13 14
15 9
16 12
11 16
14 0
2 4
1 4
7 11
5 4
0 6
2 1
18 5
15 7
3 3
17 8
0 3
13 1...

output:

675593564

result:

ok 1 number(s): "675593564"

Test #40:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

100
18 2
8 17
14 3
19 1
15 7
11 10
6 6
15 11
3 2
11 7
2 19
20 9
6 18
14 11
4 0
11 16
12 16
9 17
1 4
8 0
4 10
14 11
18 12
15 4
7 20
19 4
10 0
5 3
12 2
16 4
3 14
14 13
11 9
1 9
13 18
17 0
9 4
7 0
14 12
16 8
0 11
19 0
16 17
10 20
6 15
5 13
5 20
7 12
13 13
19 17
3 14
15 4
9 5
12 0
4 8
11 20
7 11
15 0
5 ...

output:

728706610

result:

ok 1 number(s): "728706610"

Test #41:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

100
12 15
9 6
13 20
7 14
18 8
8 10
11 7
9 11
8 4
19 17
7 14
20 12
20 17
5 4
5 14
8 12
12 10
8 7
17 4
10 3
15 20
0 16
10 16
7 17
19 0
14 6
17 1
18 5
6 2
15 19
12 18
20 11
9 6
14 7
4 17
12 1
18 6
6 13
16 17
2 11
9 16
18 20
8 11
6 17
6 16
19 18
17 12
1 7
19 9
8 12
19 9
17 8
6 9
2 6
10 12
12 12
20 10
0 ...

output:

121633147

result:

ok 1 number(s): "121633147"

Test #42:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

100
12 12
12 19
15 20
8 17
7 13
13 17
11 19
3 7
13 12
4 11
3 7
18 11
0 11
5 9
9 13
13 0
11 1
1 0
15 18
7 9
18 13
0 20
1 4
4 18
6 20
2 18
2 3
12 15
8 16
1 8
16 19
0 6
4 20
7 8
2 1
13 17
11 1
13 2
20 3
4 19
7 13
15 7
6 10
5 12
13 14
15 11
13 12
4 4
13 0
6 10
8 16
10 11
1 6
6 9
7 18
1 17
19 19
13 15
12...

output:

660618691

result:

ok 1 number(s): "660618691"

Test #43:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

100
567775692 225148306
284853961 74506045
127658181 266239688
68021672 140236565
236895051 864333041
883174534 764245141
405290517 409535649
943170619 801826942
292146623 930092201
361388966 679652079
982646932 930843436
812470239 512105172
323294773 217941822
136514187 289551923
700526170 82005015...

output:

574679222

result:

ok 1 number(s): "574679222"

Test #44:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

100
20861893 452784880
795349774 765697917
287387681 75293275
243113141 318332276
321267732 728212159
776993902 430316106
885761159 802781441
829690946 925865187
738434872 790975048
97458246 209644523
393675255 876337658
711951195 368488549
364627247 404759025
332441448 154566013
91452688 471397303
...

output:

259816346

result:

ok 1 number(s): "259816346"

Test #45:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

100
105351876 49017674
937249366 383260859
447117181 884346864
639542974 496427987
700607706 182025859
597184343 464983290
29795311 196027231
84807493 459968849
553319340 20454113
497091039 739636969
436107358 863301077
242835930 856275707
700927014 886543519
601997637 429645521
892444624 459180935
...

output:

736099588

result:

ok 1 number(s): "736099588"

Test #46:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

100
968503496 571621540
784181666 74452729
680475609 693400451
446038223 43119917
153576607 45904977
122407491 131054255
510265953 589273023
266295113 289039802
294574880 586369669
233160319 269629414
847135682 440199080
142316886 417691793
742259488 704764502
797924898 999692321
914774924 110528079...

output:

933435086

result:

ok 1 number(s): "933435086"

Test #47:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

100
52993478 167854333
926081259 765644601
135172400 871050258
916096984 221215628
532916580 499718678
237565223 165721439
359332815 277486106
447782732 118110755
740863129 815848736
264196892 168218079
553131296 795758719
336765133 274075170
78559254 186548996
67481086 569739120
715766859 761875224...

output:

940703840

result:

ok 1 number(s): "940703840"

Test #48:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100
211112388 395490908
67980850 88240251
663498120 680103845
722592233 694278631
690918190 363597796
131384592 831792405
429738040 39328117
334303060 242149001
482118669 381764291
663829684 993177817
595563400 372656722
867649869 130458548
488487948 668333490
263408347 139785919
811726086 44626148
...

output:

553761448

result:

ok 1 number(s): "553761448"

Test #49:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

100
295602371 623127482
209880442 74399413
823227620 489157433
824054774 872374343
70258163 817411498
951575033 161426881
910208682 137606617
884386899 702623735
928406918 611243357
399898965 523170261
6591722 728216361
62098116 691874634
824787715 486554473
459335608 414865426
202652605 695973292
3...

output:

37494665

result:

ok 1 number(s): "37494665"

Test #50:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

100
748688574 219360275
56812743 765591284
982957120 298211020
999146243 50470053
523227064 976257907
476798181 827497846
759275543 825819701
770907227 531694688
374695166 472126204
725902829 53162706
712587338 10147072
592982852 843225304
866120189 673371675
728891797 911283298
3644540 978724217
43...

output:

973784935

result:

ok 1 number(s): "973784935"

Test #51:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

100
538211264 446996850
198712335 88186935
511282839 475860827
100608783 228565764
902567038 135104316
296988621 862165031
534713476 219065492
952394847 360765642
115950706 406637979
830568330 583155152
460052149 292077783
492463808 699608681
907452664 860188878
924819058 481330097
25974839 63007136...

output:

141497771

result:

ok 1 number(s): "141497771"

Test #52:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

100
312890580 393896274
480926841 664002432
584591137 999156300
632165548 387307346
849006310 582498034
431088142 993081763
615301849 286914158
544485567 69496805
166251264 396221725
576857318 296217058
622182283 709200948
311843446 303202668
526969939 826200595
15104678 540575137
400327406 96635078...

output:

808258237

result:

ok 1 number(s): "808258237"

Test #53:

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

input:

2000
8 14
18 0
10 10
1 8
5 11
14 4
5 6
10 3
20 19
16 12
20 10
5 7
16 15
2 17
1 2
19 9
0 0
10 4
2 11
19 13
16 15
14 20
17 14
2 5
8 16
17 11
4 7
9 4
16 13
5 0
4 1
11 11
14 14
17 1
12 3
13 13
15 10
2 1
3 3
13 18
4 16
15 14
20 14
0 5
2 3
0 9
6 7
10 15
2 11
3 15
18 17
6 11
3 12
7 9
14 20
16 10
7 18
9 3
3...

output:

958208391

result:

ok 1 number(s): "958208391"

Test #54:

score: 0
Accepted
time: 69ms
memory: 3760kb

input:

2000
13 15
17 7
2 16
19 20
16 3
20 0
17 11
0 2
4 20
20 7
3 15
18 17
11 8
13 13
0 0
15 18
1 4
1 12
19 17
9 0
15 12
13 6
12 8
18 19
0 16
10 17
1 15
11 1
14 7
15 5
2 18
11 6
13 13
15 9
10 16
10 15
1 11
1 8
9 2
6 20
0 14
4 2
18 12
10 0
2 0
14 20
4 6
10 16
2 16
9 20
1 13
8 16
9 15
5 9
20 1
13 3
11 6
5 19...

output:

715234756

result:

ok 1 number(s): "715234756"

Test #55:

score: 0
Accepted
time: 71ms
memory: 3724kb

input:

2000
6 4
2 4
6 14
9 7
1 3
17 4
0 13
16 10
0 20
8 19
11 20
15 1
6 13
3 9
2 15
8 7
2 8
9 4
3 14
17 4
13 18
8 14
15 14
13 17
20 2
7 19
3 18
17 19
15 15
4 7
0 5
8 9
7 12
17 0
7 12
16 12
7 8
17 7
2 10
20 18
12 11
6 10
19 15
17 11
6 1
7 2
2 6
9 3
10 0
2 0
17 12
14 4
7 17
4 20
10 20
7 13
19 2
2 17
20 4
6 2...

output:

22101785

result:

ok 1 number(s): "22101785"

Test #56:

score: 0
Accepted
time: 69ms
memory: 3960kb

input:

2000
10 9
13 1
10 3
2 10
15 13
3 4
8 1
19 9
4 13
20 7
8 0
11 6
10 7
19 19
18 5
8 0
3 11
13 12
17 16
20 20
8 16
2 0
10 8
7 6
4 1
5 0
4 5
2 12
12 9
14 8
6 17
8 20
2 3
11 16
8 8
1 13
9 1
12 6
17 1
5 17
0 17
20 2
13 18
7 2
6 2
4 9
17 13
4 11
5 17
16 18
0 7
19 4
17 12
2 3
4 1
5 15
2 7
15 20
0 17
20 7
12 ...

output:

173081608

result:

ok 1 number(s): "173081608"

Test #57:

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

input:

2000
15 19
12 12
14 6
20 5
13 5
0 8
20 2
19 4
0 9
20 6
16 5
11 7
5 17
9 15
20 20
4 2
8 3
4 8
13 8
15 7
6 13
18 8
5 2
2 0
17 0
2 14
2 13
8 14
9 12
7 17
4 1
8 15
18 19
13 6
10 12
6 7
19 19
11 13
2 0
19 6
13 19
5 15
11 12
10 14
1 4
6 8
16 12
3 7
17 5
9 2
12 3
4 13
19 14
17 10
19 3
6 4
9 8
12 10
13 18
2...

output:

689909392

result:

ok 1 number(s): "689909392"

Test #58:

score: 0
Accepted
time: 71ms
memory: 3992kb

input:

2000
20 20
2 9
14 16
9 8
7 18
6 12
11 4
1 20
5 10
12 18
20 19
7 12
3 1
20 11
15 18
18 12
13 7
12 20
14 14
18 11
17 19
16 6
8 0
18 18
17 3
20 16
16 17
10 19
10 7
1 18
18 1
1 1
12 10
11 14
11 8
4 4
1 20
6 20
17 12
13 8
14 17
11 20
8 11
16 9
1 1
3 11
6 19
7 15
13 10
2 7
20 2
2 18
0 9
16 14
17 19
17 14
...

output:

525822114

result:

ok 1 number(s): "525822114"

Test #59:

score: 0
Accepted
time: 71ms
memory: 3732kb

input:

2000
3 1
9 19
1 6
3 16
0 10
12 8
2 5
0 20
10 2
4 10
3 20
4 17
7 16
18 3
17 8
14 8
10 11
3 8
11 3
13 15
12 17
11 10
3 15
12 16
9 7
18 18
13 13
16 12
4 14
7 2
15 5
1 7
7 8
13 9
8 4
6 5
3 1
5 19
19 19
6 11
6 2
0 16
6 10
10 0
13 2
17 15
8 19
2 11
8 7
8 12
11 2
8 6
19 12
10 1
6 4
19 16
8 13
1 12
13 2
13 ...

output:

587508108

result:

ok 1 number(s): "587508108"

Test #60:

score: 0
Accepted
time: 71ms
memory: 3724kb

input:

2000
17 10
7 17
5 12
0 3
2 3
6 12
6 15
3 15
5 3
20 5
7 4
8 5
2 17
9 20
15 3
6 18
16 14
11 0
7 13
16 14
10 19
10 0
19 0
11 14
17 2
15 20
11 20
1 9
1 8
4 3
17 13
5 10
2 7
15 0
6 0
12 7
9 19
0 1
13 2
20 9
19 4
10 3
7 12
17 16
13 3
10 5
19 18
5 19
16 12
1 13
6 14
14 6
8 6
16 0
0 10
8 5
16 13
19 2
14 15
...

output:

895833705

result:

ok 1 number(s): "895833705"

Test #61:

score: 0
Accepted
time: 69ms
memory: 3960kb

input:

2000
0 16
18 2
5 2
10 10
0 3
16 8
18 3
3 14
10 20
16 4
8 9
0 11
14 10
3 16
14 1
3 3
13 14
19 16
12 5
20 18
9 16
0 4
1 15
2 11
13 13
4 5
4 3
16 14
6 11
10 8
19 0
19 9
0 19
9 8
3 13
17 17
15 12
7 9
11 10
5 7
6 2
12 8
1 15
2 7
12 9
3 8
17 4
1 15
11 17
15 18
10 18
20 19
10 9
14 12
19 12
10 19
20 1
11 1
...

output:

263930283

result:

ok 1 number(s): "263930283"

Test #62:

score: 0
Accepted
time: 70ms
memory: 3680kb

input:

2000
7 11
11 8
17 17
10 0
9 19
6 11
3 8
3 15
5 14
13 17
12 10
13 1
3 10
4 20
11 11
8 0
17 15
12 11
3 4
17 14
3 4
6 9
0 20
11 14
6 1
4 1
8 0
7 1
3 5
10 18
17 15
1 15
1 11
4 9
14 7
16 1
11 9
10 1
12 15
7 5
3 17
1 19
3 4
14 6
1 1
5 7
9 16
2 13
19 6
7 11
10 1
9 5
19 19
9 11
5 8
10 14
15 2
17 3
19 3
17 1...

output:

728560648

result:

ok 1 number(s): "728560648"

Test #63:

score: 0
Accepted
time: 313ms
memory: 3824kb

input:

2000
565117304 125814888
586097543 963853833
196590927 534233702
214202996 417607347
217344493 833980730
579124249 288058518
353693152 141368
931819726 549915952
94544449 722578470
980780801 815164329
127100054 282936210
827026159 411803214
977935317 679355574
614170675 304267823
705937537 243835557...

output:

788046078

result:

ok 1 number(s): "788046078"

Test #64:

score: 0
Accepted
time: 309ms
memory: 3768kb

input:

2000
788436877 974052673
829967590 765398156
269539766 537102347
622553467 666401120
874506660 16535909
781745304 155828426
850228329 124196813
779920379 156915212
379354853 68702931
983430000 113473197
140287884 730520408
843204556 903083650
638242565 250586437
440501645 455899967
741443011 9088761...

output:

595061241

result:

ok 1 number(s): "595061241"

Test #65:

score: 0
Accepted
time: 317ms
memory: 3832kb

input:

2000
421821866 527323166
368804927 566942480
678925093 834938283
104532865 915194893
163072606 977752725
320802846 433663751
273134577 543219551
964457522 353849056
664165257 119860101
649642710 411782067
112006517 136635407
859382954 762960305
372178740 158253789
971865323 943968600
408352265 57391...

output:

125819098

result:

ok 1 number(s): "125819098"

Test #66:

score: 0
Accepted
time: 316ms
memory: 3824kb

input:

2000
350174147 375560950
317707681 73519512
751873932 132774218
512883337 532584885
451638553 160307904
523423900 301433659
769669754 962242288
517590884 255815609
612539173 171017271
20888128 5058227
420161639 879186897
875561351 959273449
737518696 729484653
798196293 432037231
738825031 238957199...

output:

85486072

result:

ok 1 number(s): "85486072"

Test #67:

score: 0
Accepted
time: 315ms
memory: 3832kb

input:

2000
942089940 223798734
561577727 170031127
529855479 430610155
994862736 781378658
445237208 711459303
62481442 874236276
561172221 749861245
775756954 789185942
897349577 885737953
687100840 303367096
433349469 695367313
891739748 745521177
471454872 300715516
329559970 878636667
110766993 609030...

output:

430396548

result:

ok 1 number(s): "430396548"

Test #68:

score: 0
Accepted
time: 322ms
memory: 4052kb

input:

2000
575474929 777069228
100415065 676608160
307837025 359849871
403213206 398768650
733803155 894014482
265102496 742006184
689111178 168883981
960294097 691152494
182159980 231862414
689750039 601675965
110100810 732886093
834289217 605397832
836794828 913415577
155890939 366705299
441239760 56903...

output:

521976850

result:

ok 1 number(s): "521976850"

Test #69:

score: 0
Accepted
time: 316ms
memory: 3860kb

input:

2000
503827210 330339720
49317819 109556263
85818572 657685807
885192605 647562423
685932614 445165881
99127331 609776092
185646354 292939427
513427459 593119047
466970384 283019584
355962749 194952125
418255932 844033802
850467615 96678267
570731004 484646440
687254618 854773932
108149014 307707768...

output:

807886658

result:

ok 1 number(s): "807886658"

Test #70:

score: 0
Accepted
time: 313ms
memory: 3896kb

input:

2000
432179491 178577505
293187865 911100588
790171192 660554451
998575785 559919707
974498561 37786476
301748385 182578708
977148823 80558384
66560821 421456671
46748080 629144046
22175459 493260994
726411054 250148801
866646012 587958703
231038251 55877303
808552879 637809856
143654488 972748316
7...

output:

984099271

result:

ok 1 number(s): "984099271"

Test #71:

score: 0
Accepted
time: 314ms
memory: 3828kb

input:

2000
360531772 731847998
832025203 417677620
568152738 958390388
480555183 513746188
263064507 588937876
840805928 755381325
105087778 499581121
956130672 323423223
700154704 975268508
319791951 791569864
403162395 697732998
882824409 447835358
670007135 332140876
339916556 789441999
810563743 63778...

output:

432195691

result:

ok 1 number(s): "432195691"

Test #72:

score: 0
Accepted
time: 310ms
memory: 3824kb

input:

2000
850674853 757678182
614338058 932025149
494408266 474957686
385076647 602473996
985457496 474129209
664895614 408386263
886629199 321087388
862987220 229618462
498766602 984642359
149906363 43490627
906658497 23053563
464000957 741736344
91234120 651257405
186319293 147794914
15917570 300028244...

output:

312721957

result:

ok 1 number(s): "312721957"

Test #73:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

3
0 0
0 0
1 1

output:

10

result:

ok 1 number(s): "10"

Test #74:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5
0 0
0 0
1 1
1 1
1 1

output:

52

result:

ok 1 number(s): "52"

Test #75:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

3
0 0
0 0
0 0

output:

7

result:

ok 1 number(s): "7"