QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130775#4956. Geometry of TrianglesckisekiAC ✓95ms24096kbC++202.4kb2023-07-25 04:22:512023-07-25 04:22:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-25 04:22:53]
  • 评测
  • 测评结果:AC
  • 用时:95ms
  • 内存:24096kb
  • [2023-07-25 04:22:51]
  • 提交

answer

// An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    map<pair<pair<int,int>,pair<int,int>>, int> mp;
    const auto readpt = []() {
        int x, y;
        cin >> x >> y;
        return make_pair(x, y);
    };

    vector<vector<int>> g(n);
    vector<int64_t> a(n);

    for (int i = 0; i < n; i++) {
        pair<int,int> p[3];
        for (int j = 0; j < 3; j++)
            p[j] = readpt();

        {
            complex<int64_t> c[3];
            for (int j = 0; j < 3; j++) {
                c[j] = {p[j].first, p[j].second};
            }
            a[i] = abs(imag(conj(c[2] - c[0]) * (c[1] - c[0])));
            debug(a[i]);
        }

        for (int j = 0; j < 3; j++) {
            auto e = make_pair(p[j], p[(j + 1) % 3]);
            if (e.first > e.second) swap(e.first, e.second);
            if (auto it = mp.find(e); it != mp.end()) {
                int x = it->second;
                g[i].emplace_back(x);
                g[x].emplace_back(i);
                debug(i, x);
            } else {
                mp[e] = i;
            }
        }
    }

    const auto dfs = [&](auto self, int i, int f = -1) -> pair<int64_t,int64_t> {
        // F = not take me, S = take me
        int64_t F = 0, S = a[i];
        if (g[i].size() != 3)
            F = 1e18;
        for (int j: g[i]) {
            if (j == f) continue;
            auto [sF, sS] = self(self, j, i);
            S += min(sF, sS);
            F += sS;
        }
        return {F, S};
    };

    auto [F, S] = dfs(dfs, 0);
    int64_t ans = min(F, S);
    cout << ans/2 << '.' << (ans%2==1 ? '5' : '0') << '\n';

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3568kb

input:

4
0 0 0 10 10 0
10 10 0 10 10 0
10 10 0 10 0 20
10 10 20 0 10 0

output:

150.0

result:

ok single line: '150.0'

Test #2:

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

input:

3
0 0 0 10 10 0
10 10 0 10 10 0
10 10 20 0 10 0

output:

150.0

result:

ok single line: '150.0'

Test #3:

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

input:

1
0 0 1 0 0 1

output:

0.5

result:

ok single line: '0.5'

Test #4:

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

input:

10
100 100 120 100 110 110
120 100 120 110 110 110
100 100 110 110 100 110
100 100 110 92 120 100
110 92 130 80 120 100
120 100 140 105 120 110
120 110 115 120 110 110
110 110 105 120 100 110
100 110 80 110 100 100
100 100 90 80 110 92

output:

680.0

result:

ok single line: '680.0'

Test #5:

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

input:

10
100 100 120 100 110 110
120 100 115 106 110 110
100 100 110 110 105 106
100 100 110 98 120 100
110 98 130 80 120 100
120 100 140 105 115 106
115 106 115 120 110 110
110 110 105 120 105 106
105 106 80 110 100 100
100 100 90 80 110 98

output:

477.5

result:

ok single line: '477.5'

Test #6:

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

input:

2
0 0 10 0 10 10
10 0 20 0 10 10

output:

100.0

result:

ok single line: '100.0'

Test #7:

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

input:

98
-10297 48928 -44697 22410 -42983 25543
-2626 -49932 -47201 16496 3296 -49892
13006 -48279 12725 48353 16748 47111
31377 -38929 37976 -32524 37690 -32855
12765 -48343 12725 48353 13006 -48279
3296 -49892 12765 -48343 8278 -49310
3296 -49892 -47201 16496 12765 -48343
49944 2352 44253 23273 46389 18...

output:

2175748284.0

result:

ok single line: '2175748284.0'

Test #8:

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

input:

98
13276 -48206 16088 -47341 15425 -47562
49444 7430 8461 49278 12723 48354
-17292 -46916 -44724 22357 2311 49946
-49944 -2380 -49919 2860 -49726 5232
4036 -49837 10419 -48903 5741 -49670
-44724 22357 -47159 16615 -46946 17208
-5447 49702 -13948 48015 -13119 48248
49529 -6844 49954 2129 49989 1037
-...

output:

2944537065.0

result:

ok single line: '2944537065.0'

Test #9:

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

input:

98
48575 -11855 49337 -8121 49114 -9373
36023 -34676 46738 -17765 46196 -19130
-31888 -38514 -49449 7415 -48679 11424
25904 42767 -41035 28569 -27929 41474
25904 42767 7253 49472 7798 49389
25180 43198 15570 47514 19002 46249
13764 -48070 49848 3904 49862 -3714
42265 26715 37097 33523 37941 32566
-2...

output:

2767972131.5

result:

ok single line: '2767972131.5'

Test #10:

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

input:

98
3408 -49885 -13774 48066 8168 49329
-49025 -9834 -23192 -44298 -45001 -21797
-8186 -49327 3408 -49885 -2046 -49960
49948 -2289 49780 4685 49861 3737
-47848 14517 -49683 5636 -49633 6055
37359 -33233 48031 -13897 39648 -30465
15207 -47633 26914 -42140 22194 -44806
-21174 -45297 -50001 -189 -50000 ...

output:

3723649526.0

result:

ok single line: '3723649526.0'

Test #11:

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

input:

98
-49448 -7427 -49337 8129 -48777 11004
-46566 18217 -47279 16276 -46751 17735
-33508 37113 -44053 23656 -43742 24225
-49448 -7427 -48099 13666 -46566 18217
48346 12761 46870 17417 47184 16548
-50001 -425 -49337 8129 -49583 -6461
13096 48256 8968 49191 12502 48413
-49448 -7427 -287 50001 -4442 -498...

output:

2227403143.5

result:

ok single line: '2227403143.5'

Test #12:

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

input:

98
-35748 -34962 -14522 -47847 -17452 -46858
-29695 -40231 -23722 -44018 -28350 -41189
15704 47471 -17500 46839 12665 48371
35186 35526 -47073 16864 -46693 17889
30403 -39697 36415 -34266 33946 -36714
-28350 -41189 -23722 -44018 -26149 -42621
-49375 -7896 -49600 6335 -49163 -9126
33206 37383 -31862 ...

output:

2954676821.5

result:

ok single line: '2954676821.5'

Test #13:

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

input:

98
-28686 40956 -35039 35673 -31559 38786
-12739 -48354 39982 -30029 30606 -39542
-8396 -49294 10225 -48947 4728 -49779
47785 14727 35289 35425 38722 31637
-8396 -49294 4728 -49779 2857 -49922
-43553 24566 -49746 5070 -49708 5429
16902 47059 16229 47296 16612 47162
32688 -37839 39982 -30029 39827 -3...

output:

1855736008.0

result:

ok single line: '1855736008.0'

Test #14:

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

input:

98
44039 23681 41184 28357 43334 24948
18256 -46552 41847 -27370 38685 -31683
49931 -2671 -1295 49986 49996 -811
-47845 -14533 -37176 33440 -38514 -31891
-7869 49379 -25976 42726 -18746 46356
-38514 -31891 -37176 33440 17879 -46698
-29805 -40150 -14464 -47866 -17445 -46862
-47673 -15087 -39341 -3086...

output:

3355005733.0

result:

ok single line: '3355005733.0'

Test #15:

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

input:

98
-49155 -9181 -48687 11404 -47885 14405
-45469 -20809 -26312 -42522 -43197 -25190
-25744 -42869 944 -49996 -16770 -47109
-13420 48169 -17969 46664 -14944 47718
9619 -49071 29469 -40398 17813 -46724
-25744 -42869 18043 46635 944 -49996
3657 49870 -12423 48436 -3959 49847
-43197 -25190 -26312 -42522...

output:

1717088404.0

result:

ok single line: '1717088404.0'

Test #16:

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

input:

98
-33106 37476 -48709 11308 -44830 22153
44475 -22856 31360 38947 32309 38164
48863 -10621 42387 26527 42612 26163
-4363 -49814 16067 -47353 -2461 -49944
9316 49128 -4860 49767 -2856 49922
-32879 37675 -48890 10499 -48709 11308
-48412 -12519 23965 43887 24912 43356
-24419 43636 -30328 39757 -25271 ...

output:

2322181738.0

result:

ok single line: '2322181738.0'

Test #17:

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

input:

98
49753 5012 -7796 49393 48754 11112
25233 -43172 -31284 39011 49599 -6359
20100 -45788 -35175 35542 -31284 39011
44451 22904 41406 28035 44161 23456
-41070 -28528 -38746 -31612 -40675 -29088
31474 -38857 46967 -17163 41944 -27224
-40675 -29088 -38746 -31612 -40468 -29375
49599 -6359 -31284 39011 4...

output:

3910877045.0

result:

ok single line: '3910877045.0'

Test #18:

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

input:

98
-47330 16138 -48481 12253 -48090 13709
-43002 25521 -48481 12253 -47330 16138
-14863 -47746 7767 -49399 -9611 -49073
-33242 -37357 -26807 -42213 -30259 -39812
-49542 -6792 -48657 11535 -22141 44836
49898 -3267 48827 10789 49971 1836
-48119 -13608 -33935 -36729 -41719 -27569
34953 35760 33223 3737...

output:

1677580422.0

result:

ok single line: '1677580422.0'

Test #19:

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

input:

98
-26685 -42292 26566 -42366 -4111 -49837
49823 4267 49142 9254 49591 6427
49886 -3463 -17180 46962 44873 22066
-27112 42018 -31975 38448 -30436 39677
-49974 -1809 -48938 -10281 -49795 -4599
-42923 -25657 -44475 22860 49368 -7962
42914 -25670 47434 -15831 47404 -15920
-26455 -42436 -20686 -45528 -2...

output:

2280208999.5

result:

ok single line: '2280208999.5'

Test #20:

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

input:

98
12182 -48500 24963 -43330 18847 -46319
12182 -48500 18847 -46319 16432 -47230
-8590 49262 -15364 47587 -15025 47695
29490 40384 -49882 3531 -45493 20761
-28158 -41326 -20616 -45559 -27540 -41740
9874 49021 -43315 24988 9559 49083
-6447 -49589 2343 -49952 -2618 -49938
-7291 -49472 37809 -32727 -64...

output:

3519295643.0

result:

ok single line: '3519295643.0'

Test #21:

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

input:

98
49989 1333 4250 49826 9834 49030
25451 43045 22119 44848 22268 44775
43029 -25479 43960 -23838 43101 -25357
-1720 49977 -12842 48329 -5648 49687
-33343 37269 -46932 17266 -44086 23604
46357 18752 40029 29971 45597 20532
43960 -23838 -15423 47569 -1060 49995
-29688 40241 -31152 39118 -30913 39307
...

output:

2822491894.5

result:

ok single line: '2822491894.5'

Test #22:

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

input:

98
28781 -40895 39631 -30497 38449 -31974
-32762 -37782 -24246 -43737 -27919 -41489
-24246 -43737 -3735 49867 -2386 49950
39631 -30497 -515 50004 3636 49874
39268 30962 36681 33987 38652 31727
48220 -13249 49933 -2717 49456 -7401
10226 48950 3636 49874 10076 48981
28781 -40895 38449 -31974 31721 -38...

output:

2787559341.5

result:

ok single line: '2787559341.5'

Test #23:

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

input:

98
-45171 -21457 -7469 -49448 -7703 -49412
-44593 -22635 -41818 -27425 -41917 -27273
-44628 -22566 -8187 -49334 -44593 -22635
21436 45180 15957 47393 18710 46375
27768 41589 -25896 42780 -14071 47987
-45171 -21457 -7703 -49412 -44628 -22566
49988 1409 48579 11868 49373 7940
50007 118 46960 17191 485...

output:

1967221472.5

result:

ok single line: '1967221472.5'

Test #24:

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

input:

98
-14322 47913 -44253 23291 -39621 30512
-29539 40352 -39621 30512 -38638 31748
-30186 -39871 -49751 5072 -49598 6395
49949 2408 49400 7773 49924 2896
-14322 47913 -39621 30512 -29539 40352
14596 -47831 22202 -44810 17887 -46700
49400 7773 22263 44778 24905 43364
37497 -33087 47060 -16917 37705 -32...

output:

2291345099.0

result:

ok single line: '2291345099.0'

Test #25:

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

input:

98
419 -50008 -40934 28728 31324 -38983
47129 16725 36276 34423 46991 17108
49015 9919 33340 37273 47755 14842
-30164 -39889 -19382 -46101 -25611 -42954
12385 -48451 31324 -38983 13849 -48054
31324 -38983 38121 -32368 33672 -36975
33299 37310 26332 42514 32663 37868
-41947 27228 -48699 11372 -48517 ...

output:

3098865412.0

result:

ok single line: '3098865412.0'

Test #26:

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

input:

98
40444 -29414 19568 46021 20903 45430
40444 -29414 6357 49603 19426 46081
-49771 -4882 -19727 45953 -48986 -10066
40444 -29414 20903 45430 40492 -29348
1898 -49973 33850 -36811 27458 -41797
-44027 23718 -48826 10815 -44223 23350
-49893 -3405 -49662 5889 -48826 10815
-28058 41396 -31761 38628 -2968...

output:

3056954952.0

result:

ok single line: '3056954952.0'

Test #27:

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

input:

98
37294 33318 32134 38319 32283 38193
-28036 41412 -32620 37907 -29247 40566
-15186 47648 -20004 45835 -19727 45954
-35362 -35364 46301 18898 46455 18518
22333 -44747 25138 -43233 24645 -43516
19222 46168 -24967 43332 15676 47489
42149 -26915 49403 7765 42915 -25677
-32620 37907 -38209 32266 -34805...

output:

2421580991.5

result:

ok single line: '2421580991.5'

Test #28:

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

input:

98
31376 -38943 36455 -34235 31500 -38843
6053 49642 -1567 49985 434 50008
40459 29394 36404 34288 39801 30279
-11167 48747 -19005 46258 -13123 48257
-19005 46258 -24940 43347 -22000 44911
-7758 49404 -24940 43347 -19005 46258
-6222 49621 -42360 26583 -28702 40953
29135 40646 9189 49158 24766 43446
...

output:

2771612606.0

result:

ok single line: '2771612606.0'

Test #29:

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

input:

98
-40836 28871 -45079 21656 -41856 27371
-28282 41246 -40836 28871 -37365 33241
-45891 19878 -47166 16629 -46296 18917
-48418 -12525 16260 -47294 12796 -48347
-41856 27371 -45079 21656 -42096 27000
-48442 12431 -49036 9830 -48960 10198
38692 -31686 41261 -28260 40155 -29811
-45079 21656 -48442 1243...

output:

2389889320.5

result:

ok single line: '2389889320.5'

Test #30:

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

input:

98
-49949 -2504 -48086 -13745 -49135 -9325
-40825 -28887 -29685 -40249 -33484 -37148
15503 47547 9295 49139 10064 48987
21135 45325 16320 47273 18409 46499
9295 49139 -40825 -28887 -49949 -2504
8697 -49249 12570 -48406 11660 -48633
47243 16407 45023 21770 45143 21521
-29111 -40666 -25101 -43257 -268...

output:

3404254108.0

result:

ok single line: '3404254108.0'

Test #31:

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

input:

98
22684 44571 -14898 47741 -1931 49974
-27951 -41473 -612 -50009 -5944 -49658
39546 -30615 22684 44571 35180 35546
-49417 -7698 -41725 -27574 -43753 -24226
-48094 13720 -41725 -27574 -49417 -7698
-14898 47741 -41725 -27574 -48094 13720
30736 -39453 35368 -35360 33186 -37415
-30277 -39807 39546 -306...

output:

2828063987.0

result:

ok single line: '2828063987.0'

Test #32:

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

input:

98
43835 24075 6526 -49585 32219 38250
42020 27120 34592 36119 40336 29565
17310 -46921 31138 -39136 26612 -42344
43930 -23903 47731 -14931 47483 -15702
-7435 49456 -19974 45850 -16214 47311
6526 -49585 38410 -32029 43835 24075
4425 49815 6526 -49585 -35443 -35286
43930 -23903 47483 -15702 45153 -21...

output:

2809028298.0

result:

ok single line: '2809028298.0'

Test #33:

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

input:

98
40776 -28959 44501 -22825 41738 -27555
47597 15356 41776 27495 42216 26815
48722 11290 41776 27495 47597 15356
46985 -17138 47917 -14325 47552 -15495
8827 49227 -46383 -18708 -641 50008
50005 -845 48722 11290 50010 521
-3183 -49912 5966 -49656 1470 -49992
36819 33847 11784 48604 18573 46436
-2441...

output:

3280351832.0

result:

ok single line: '3280351832.0'

Test #34:

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

input:

98
-1254 -49998 1448 -49993 -110 -50013
45065 -21690 46405 -18650 45750 -20203
24547 43574 230 50012 7164 49497
-30748 39445 -49959 2338 -31556 38801
46594 -18174 49980 -1810 47497 -15662
46405 -18650 35508 35220 49957 2364
-49959 2338 -28690 -40966 -48737 -11229
49957 2364 35508 35220 48709 11345
-...

output:

3026999492.5

result:

ok single line: '3026999492.5'

Test #35:

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

input:

98
-32628 -37907 45073 -21676 30508 39631
45894 -19878 48534 -12074 47704 -15023
24528 43586 12584 48404 15133 47669
-40622 29176 -47380 16018 -42525 26326
49318 -8314 43231 25149 49740 5226
49318 -8314 49740 5226 49728 -5338
-31689 -38694 -10062 -48992 -24506 -43600
-15877 47427 -16962 47050 -16474...

output:

2733694149.0

result:

ok single line: '2733694149.0'

Test #36:

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

input:

98
-49220 8877 -48668 -11529 -49885 -3603
-34794 35928 -36225 34484 -35701 35026
47268 16343 -48668 -11529 16080 47358
41329 -28166 43268 -25085 41735 -27560
-44119 23557 -48124 13622 -44405 23014
-4386 49821 -8655 49259 -5677 49690
12392 -48455 14181 -47962 13663 -48112
38003 -32515 43268 -25085 41...

output:

2803904546.5

result:

ok single line: '2803904546.5'

Test #37:

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

input:

98
11158 48754 3630 49883 5305 49732
31131 -39145 36058 -34660 32938 -37638
17828 -46730 22412 -44713 19634 -46000
44767 22302 39013 31295 40999 28645
33651 -37001 34589 -36127 34053 -36632
-3009 -49925 2016 -49975 518 -50013
31030 39225 29719 40227 30028 39997
29494 40392 28268 41259 28862 40846
-3...

output:

2637249711.0

result:

ok single line: '2637249711.0'

Test #38:

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

input:

98
-29835 -40143 -25659 -42932 -27939 -41485
-8805 -49235 424 -50014 -6467 -49596
-7486 49451 -9020 49195 -8309 49320
-19660 -45990 -12784 -48354 -17848 -46723
-43589 -24526 -34568 -36148 -41554 -27836
-20521 45611 -24314 43707 -21839 44995
-39262 30984 -34568 -36148 -42958 25615
25998 -42727 32251 ...

output:

3061692497.0

result:

ok single line: '3061692497.0'

Test #39:

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

input:

98
43121 -25340 45906 19854 49898 3420
49898 3420 48582 11888 49148 9273
-6080 49645 -10880 48818 -9705 49065
-47233 -16455 -45991 -19659 -46955 -17232
-38671 -31721 -23057 -44385 -36317 -34391
-50001 -1246 -48364 -12751 -49213 -8932
23059 -44383 43121 -25340 33290 -37328
-37183 33452 -38458 31978 -...

output:

3648278937.5

result:

ok single line: '3648278937.5'

Test #40:

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

input:

98
-3825 -49870 4853 -49780 -2591 -49949
-47953 -14219 -46742 -17801 -46966 -17199
-10411 -48921 -4777 -49788 -9848 -49038
-23093 -44366 -4777 -49788 -10411 -48921
33447 -37187 49007 -9994 42504 -26363
-4777 -49788 4853 -49780 -3825 -49870
19652 45993 18380 46516 18643 46411
-47953 -14219 -46609 -18...

output:

2294438605.0

result:

ok single line: '2294438605.0'

Test #41:

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

input:

98
49140 9325 46705 17895 46784 17689
22171 44834 8536 49283 17619 46810
1285 50000 -42624 -26172 -15088 47687
-48532 -12101 -45011 -21813 -47892 -14427
-37070 -33579 -27153 -42006 -36304 -34406
-49500 7174 -49747 5192 -49566 6703
-44676 22490 -48457 12395 -48044 13911
-48530 12106 -49747 5192 -4950...

output:

2563191853.0

result:

ok single line: '2563191853.0'

Test #42:

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

input:

98
47666 15152 43958 23861 44529 22778
-50017 -25 -40891 -28804 -44076 -23644
-37816 -32737 -15372 -47597 -31240 -39062
-42713 26025 -50010 867 -49620 6291
3979 49858 -7521 49448 -6636 49574
19220 46176 15045 47700 16954 47055
11791 -48608 19334 46128 49221 8885
15045 47700 3979 49858 5022 49764
-40...

output:

3347268264.0

result:

ok single line: '3347268264.0'

Test #43:

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

input:

98
48957 -10246 50014 -568 49995 -1502
20066 -45817 49010 9990 50014 -568
2751 49942 -20702 45533 -10618 48878
11425 48695 2751 49942 3995 49858
-39506 -30678 -37621 -32962 -37871 -32675
2751 49942 -10618 48878 2088 49974
31378 38950 12167 48515 23091 44368
49010 9990 42809 25868 43095 25389
-49953 ...

output:

3024724811.0

result:

ok single line: '3024724811.0'

Test #44:

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

input:

98
21754 45039 14667 47818 14890 47750
-46334 -18842 -38145 -32355 -44718 -22409
38367 32088 31986 38453 37755 32806
47778 14800 45344 21111 47330 16174
-47935 14285 -49199 9017 -48050 13893
12027 -48551 15362 -47601 15217 -47648
12027 -48551 24061 -43851 15362 -47601
-48567 -11963 -303 -50018 -3006...

output:

2071895639.0

result:

ok single line: '2071895639.0'

Test #45:

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

input:

98
49931 -2959 48772 11097 49460 7455
-22567 -44639 -18973 -46282 -21286 -45265
42800 25884 24729 43478 40085 29917
-45108 21616 -49667 5930 -47241 16438
6982 49529 2017 49978 2780 49941
-39008 -31311 -31765 -38639 -38490 -31946
-16485 47224 -38815 31548 -31641 38739
-44257 -23308 -9101 -49185 -3038...

output:

3215283643.0

result:

ok single line: '3215283643.0'

Test #46:

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

input:

98
1125 50006 -4862 49782 -4175 49844
26414 -42476 29902 -40097 27583 -41726
6889 -49543 11649 -48644 7472 -49458
46492 18449 40011 30016 43980 23825
24648 43524 20693 45537 23449 44181
35903 34825 30877 39350 34271 36432
27583 -41726 29902 -40097 29210 -40604
6889 -49543 46492 18449 33343 -37285
-4...

output:

2512114343.5

result:

ok single line: '2512114343.5'

Test #47:

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

input:

98
-12767 -48364 3312 -49911 -7807 -49408
15674 47500 13037 48291 15472 47566
39810 -30285 44717 -22414 42771 -25935
-40367 29539 -41645 -27708 -43376 -24912
-40367 29539 -48681 11497 -43501 24692
-25557 -42999 3312 -49911 -16094 -47361
19849 -45913 39810 -30285 25864 -42815
14043 -48009 19849 -4591...

output:

3854541993.5

result:

ok single line: '3854541993.5'

Test #48:

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

input:

9998
983399 181455 982910 184085 983338 181785
-17660 -999845 -13331 -999912 -15552 -999880
378732 -925507 380514 -924776 379096 -925358
-198119 980178 -207166 978306 -206133 978524
-520382 853934 -529824 848108 -520700 853740
-455867 890048 -605660 795724 -456965 889485
735375 -677661 736558 -67637...

output:

224856635782.5

result:

ok single line: '224856635782.5'

Test #49:

score: 0
Accepted
time: 13ms
memory: 5160kb

input:

9999
-952240 -305354 -950588 -310459 -951938 -306294
-141977 -989871 -138575 -990353 -141439 -989948
675208 737627 672910 739724 673480 739205
451792 892123 443884 896084 449582 893239
-989175 146746 -989332 145685 -989283 146017
-999972 7610 -999988 5087 -999980 6460
675208 737627 672590 740015 672...

output:

1448350142233.5

result:

ok single line: '1448350142233.5'

Test #50:

score: 0
Accepted
time: 13ms
memory: 5180kb

input:

10000
785933 -618312 786850 -617145 786367 -617760
-829355 558723 -831213 555955 -830587 556890
-69225 -997602 1348 -1000000 -3994 -999993
-868615 -495490 -866623 -498966 -868438 -495800
-999901 -14131 -998412 -56347 -998760 -49803
-977960 -208797 -977764 -209713 -977873 -209205
990086 140462 989957...

output:

1489421900359.5

result:

ok single line: '1489421900359.5'

Test #51:

score: 0
Accepted
time: 95ms
memory: 23896kb

input:

99998
0 0 10 10 20 10
0 0 20 10 26 10
0 0 26 10 41 10
0 0 41 10 54 10
0 0 54 10 71 10
0 0 71 10 80 10
0 0 80 10 82 10
0 0 82 10 95 10
0 0 95 10 108 10
0 0 108 10 110 10
0 0 110 10 115 10
0 0 115 10 122 10
0 0 122 10 127 10
0 0 127 10 135 10
0 0 135 10 152 10
0 0 152 10 160 10
0 0 160 10 172 10
0 0 1...

output:

1273135.5

result:

ok single line: '1273135.5'

Test #52:

score: 0
Accepted
time: 91ms
memory: 23880kb

input:

99998
0 0 4 10 7 10
0 0 7 10 25 10
0 0 25 10 43 10
0 0 43 10 51 10
0 0 51 10 65 10
0 0 65 10 67 10
0 0 67 10 75 10
0 0 75 10 83 10
0 0 83 10 88 10
0 0 88 10 105 10
0 0 105 10 117 10
0 0 117 10 132 10
0 0 132 10 139 10
0 0 139 10 141 10
0 0 141 10 148 10
0 0 148 10 158 10
0 0 158 10 170 10
0 0 170 10...

output:

1328893.5

result:

ok single line: '1328893.5'

Test #53:

score: 0
Accepted
time: 81ms
memory: 23864kb

input:

99998
0 0 3 10 19 10
0 0 19 10 23 10
0 0 23 10 25 10
0 0 25 10 42 10
0 0 42 10 57 10
0 0 57 10 73 10
0 0 73 10 92 10
0 0 92 10 102 10
0 0 102 10 114 10
0 0 114 10 117 10
0 0 117 10 136 10
0 0 136 10 139 10
0 0 139 10 149 10
0 0 149 10 162 10
0 0 162 10 175 10
0 0 175 10 194 10
0 0 194 10 209 10
0 0 ...

output:

1392670.5

result:

ok single line: '1392670.5'

Test #54:

score: 0
Accepted
time: 86ms
memory: 24096kb

input:

99998
0 0 15 10 20 10
0 0 20 10 23 10
0 0 23 10 36 10
0 0 36 10 52 10
0 0 52 10 71 10
0 0 71 10 73 10
0 0 73 10 92 10
0 0 92 10 106 10
0 0 106 10 125 10
0 0 125 10 130 10
0 0 130 10 141 10
0 0 141 10 160 10
0 0 160 10 167 10
0 0 167 10 174 10
0 0 174 10 189 10
0 0 189 10 193 10
0 0 193 10 209 10
0 0...

output:

1460912.5

result:

ok single line: '1460912.5'