QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227170#7192. IntersectionPPP#AC ✓524ms62120kbC++175.7kb2023-10-27 00:30:272023-10-27 00:30:28

Judging History

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

  • [2023-10-27 00:30:28]
  • 评测
  • 测评结果:AC
  • 用时:524ms
  • 内存:62120kb
  • [2023-10-27 00:30:27]
  • 提交

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll;
typedef double ld;
struct pt{
    ld x, y;
    int id;
};
int n, m;
const int maxN = 2e5 + 10;
ll a[maxN], b[maxN], c[maxN];
bool bad[maxN];
int x[maxN], y[maxN];
ld area(pt a, pt b, pt c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
const ld eps = 1e-9;
vector<pt> convexHull(vector<pt>& pts) {
    sort(pts.begin(), pts.end(), [&](const pt &a, const pt &b) {
        return a.x + eps < b.x || (fabsl(a.x - b.x) < eps && a.y + eps < b.y);
    });
    vector<pt> npts;
    for (auto& it : pts) {
        if (!npts.empty() && fabsl(it.x - npts.back().x) < eps && fabsl(it.y - npts.back().y) < eps) {
            continue;
        }
        npts.emplace_back(it);
    }
    pts = npts;
    if (pts.size() < 3) {
        return pts;
    }
    pt pUp = pts.front(), pDown = pts.back();
    vector<pt> up{pUp}, down{pUp};
    for (size_t i = 1; i < pts.size(); ++i) {
        if (i == pts.size() - 1 || area(pUp, pts[i], pDown) < -eps) {
            while (up.size() >= 2 &&
                   area(up[up.size()-2], up.back(), pts[i]) > -eps) {
                up.pop_back();
            }
            up.push_back(pts[i]);
        }
        if (i == pts.size() - 1 || area(pUp, pts[i], pDown) > eps) {
            while (down.size() >= 2 &&
                   area(down[down.size()-2], down.back(), pts[i]) < eps) {
                down.pop_back();
            }
            down.push_back(pts[i]);
        }
    }
    assert(up.size() >= 2);
    for (size_t i = up.size() - 2; i > 0; --i) {
        down.push_back(up[i]);
    }
    return down;
}
ll det(ll a11, ll a12, ll a21, ll a22) {
    return a11 * a22 - a21 * a12;
}
pair<pair<int,int>, pair<int,int>> val_l[maxN];
pair<pair<int,int>, pair<int,int>> val_r[maxN];
pt L[maxN], R[maxN];
bool cmp(pair<int, int> a, pair <int, int> b) {
    return (1LL * a.first * b.second < 1LL * a.second * b.first);
}
void upd(int where, ll DX, ll DY, ll D) {
    pair<pair<int,int>, pair<int,int>> we = make_pair(make_pair(DX, D), make_pair(DY, D));
    if (val_l[where].first.second == 0) {
        val_l[where] = we;
        val_r[where] = we;
        L[where] = {(ld)DX / D, (ld)DY / D, -1};
        R[where] = {(ld)DX / D, (ld)DY / D, -1};
        return;
    }
    if (cmp(we.first, val_l[where].first) || (!cmp(val_l[where].first, we.first) && cmp(we.second, val_l[where].second))) {
        val_l[where] = we;
        L[where] = {(ld)DX / D, (ld)DY / D, -1};
    }

    if (cmp(val_r[where].first, we.first) || (!cmp(we.first, val_r[where].first) && cmp(val_r[where].second, we.second))) {
        val_r[where] = we;
        R[where] = {(ld)DX / D, (ld)DY / D, -1};
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m;
    if (m >= (1LL * n * (n - 1)) / 2 - 1) {
        cout << fixed << setprecision(12) << 0;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        if (b[i] == 0) {
            bad[i] = true;
        }
    }
    map<pair<int,int>,int> mp;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        assert(!mp.count({x[i], y[i]}));
        mp[{x[i], y[i]}] = true;
        mp[{y[i], x[i]}] = true;
        bad[x[i]] = true;
        bad[y[i]] = true;
    }
    vector<pt> ch;
    for (int i = 1; i <= n; i++) {
        if (bad[i]) continue;
        pt f;
        f.x = (ld)-a[i] / b[i];
        f.y = (ld)c[i] / b[i];
        f.id = i;
        ch.emplace_back(f);
    }

    vector<pt> cand;
    sort(ch.begin(), ch.end(), [&](pt& a, pt& b) {
        return a.x < b.x;
    });
    auto add = [&](int x, int y) {
        ll D = det(a[x], b[x], a[y], b[y]);
        ll DX = det(c[x], b[x], c[y], b[y]);
        ll DY = det(a[x], c[x], a[y], c[y]);
        assert(D != 0);
        if (D < 0) {
            D *= -1;
            DX *= -1;
            DY *= -1;
        }
        upd(x, DX, DY, D);
        upd(y, DX, DY, D);
    };
    for (int x = 0; x < 2; x++) {
        for (int sgn = -1; sgn <= 1; sgn += 2) {
            vector<pt> cur;
            for (auto t : ch) {
                while (cur.size() >= 2 && (cur[cur.size() - 2].x - t.x) * (cur.back().y - t.y)
                                          > (cur[cur.size() - 2].y - t.y) * (cur.back().x - t.x)) {
                    cur.pop_back();
                }
                if (!cur.empty()) {
                    add(cur.back().id, t.id);
                }
                cur.emplace_back(t);
            }
            for (auto& it : ch) {
                it.y *= -1;
            }
        }
        reverse(ch.begin(), ch.end());
    }
    for (int i = 1; i <= n; i++) {
        if (!bad[i]) continue;
        for (int j = 1; j <= n; j++) {
            if (mp.count({i, j})) continue;
            if (i == j) continue;
            add(i, j);
        }
    }
    vector<pt> fin;
    for (int i = 1; i <= n; i++) {
        if (val_l[i].first.second == 0) continue;
        fin.emplace_back(L[i]);
        fin.emplace_back(R[i]);
    }
    fin = convexHull(fin);
    ld ans = 0;
    for (int z = 0; z < fin.size(); z++) {
        ld D = sqrtl((fin[(z + 1) % fin.size()].x - fin[z].x) * (fin[(z + 1) % fin.size()].x - fin[z].x) +
                     (fin[(z + 1) % fin.size()].y - fin[z].y) * (fin[(z + 1) % fin.size()].y - fin[z].y));
        ans += D;
    }
    cout << fixed << setprecision(12) << ans << '\n';
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11872kb

input:

3 0
1 0 0
0 1 0
1 1 1

output:

3.414213562373

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #2:

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

input:

3 1
1 0 0
0 1 0
1 1 1
1 2

output:

2.828427124746

result:

ok found '2.8284271', expected '2.8284271', error '0.0000000'

Test #3:

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

input:

1 0
1 1 1

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

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

output:

4.553245560954

result:

ok found '4.5532456', expected '4.5532456', error '0.0000000'

Test #5:

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

input:

10 10
0 8 4
-10 -3 6
-1 9 -7
-8 -10 -10
-4 7 3
-8 -5 -8
9 10 -10
-6 -6 5
7 3 10
-9 -4 -7
10 9
9 4
3 1
7 2
4 7
7 8
6 5
6 1
2 5
3 5

output:

49.779204591735

result:

ok found '49.7792046', expected '49.7792046', error '0.0000000'

Test #6:

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

input:

10 10
-8 -3 3
-4 -3 9
-7 -8 8
5 1 -6
8 -8 6
-9 4 10
0 5 7
-1 -10 10
-4 6 -3
2 -8 -5
8 7
5 8
1 8
2 3
9 10
1 2
7 9
4 1
2 6
4 6

output:

19.653561435354

result:

ok found '19.6535614', expected '19.6535614', error '0.0000000'

Test #7:

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

input:

10 10
-3 2 -7
-6 5 -2
7 7 -7
-2 -6 -10
-1 1 1
-10 -4 6
-5 4 -9
-6 -5 3
8 5 -10
-3 10 9
5 10
8 9
5 2
8 3
9 6
4 10
7 2
1 6
3 4
7 1

output:

46.845684098808

result:

ok found '46.8456841', expected '46.8456841', error '0.0000000'

Test #8:

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

input:

10 10
-2 -9 -1
4 5 9
0 -6 7
7 0 -6
-10 3 8
6 5 -1
-8 9 -1
1 4 3
3 1 -1
5 5 -5
2 1
5 4
9 1
1 3
6 1
5 7
10 1
4 3
7 9
7 3

output:

85.692465262721

result:

ok found '85.6924653', expected '85.6924653', error '0.0000000'

Test #9:

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

input:

10 10
6 9 -2
1 9 -6
-7 -2 5
7 -7 -10
-2 -9 4
1 10 -1
4 8 7
6 0 8
-6 -6 -7
10 -1 0
6 1
1 7
6 2
1 9
6 10
9 4
2 3
3 8
10 8
8 9

output:

19.339340020614

result:

ok found '19.3393400', expected '19.3393400', error '0.0000000'

Test #10:

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

input:

10 10
-10 -10 9
-5 -4 5
8 5 -5
-1 3 -6
2 10 -10
0 5 0
-4 -1 3
-10 4 -8
2 -1 4
10 2 4
7 3
1 4
5 9
1 2
9 10
5 7
6 8
10 4
8 3
10 7

output:

38.662093930606

result:

ok found '38.6620939', expected '38.6620939', error '0.0000000'

Test #11:

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

input:

10 10
3 -1 -9
9 9 -6
1 9 -8
-10 -7 -6
6 -5 -7
-9 1 2
1 -7 -6
6 4 -10
8 6 -10
-2 -9 1
8 4
3 1
3 7
1 6
10 2
3 10
6 8
9 4
2 9
1 5

output:

25.912856124987

result:

ok found '25.9128561', expected '25.9128561', error '0.0000000'

Test #12:

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

input:

10 10
8 5 -6
2 -8 1
-6 -1 -6
5 7 -6
5 -5 -4
-5 -2 10
5 3 -5
-4 -7 3
-8 -6 6
-5 3 -8
3 6
10 5
6 8
5 9
2 4
2 6
9 4
2 3
6 9
10 2

output:

35.299964104203

result:

ok found '35.2999641', expected '35.2999641', error '0.0000000'

Test #13:

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

input:

10 10
9 7 0
-8 -4 -10
-8 -3 0
-10 -4 5
-9 -10 -10
10 -4 2
-1 1 10
8 0 8
8 -5 1
1 -4 1
6 9
4 3
8 6
8 3
3 1
10 4
4 9
2 4
1 9
3 5

output:

95.167961596330

result:

ok found '95.1679616', expected '95.1679616', error '0.0000000'

Test #14:

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

input:

10 10
-6 2 -3
6 4 2
-5 -7 1
0 3 5
2 -3 -8
-9 2 -9
1 -2 -1
-10 10 2
-3 8 5
-2 -2 0
8 10
10 3
5 7
5 9
4 9
5 2
6 5
6 8
5 4
1 10

output:

26.719240045470

result:

ok found '26.7192400', expected '26.7192400', error '0.0000000'

Test #15:

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

input:

100 50
6 34 -1
-55 85 -11
33 -76 -79
-23 6 -20
75 48 77
-87 35 -16
-8 -79 -49
3 -2 -8
1 45 35
-27 -79 -77
64 -51 -88
85 6 74
20 -93 -30
63 11 74
76 3 -70
67 39 53
-35 100 -95
-94 53 -85
-22 -6 43
9 -3 -69
-31 -80 55
-93 -70 29
-55 -67 21
51 -96 -6
40 -93 20
94 -54 -22
94 95 0
-48 59 55
100 -40 97
33...

output:

4237.215091379009

result:

ok found '4237.2150914', expected '4237.2150914', error '0.0000000'

Test #16:

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

input:

100 50
37 -66 -18
-83 -83 99
-100 -97 3
-80 91 73
-39 7 24
-33 93 37
-52 -70 -12
96 -24 38
-88 -97 -31
-42 -4 -1
-17 3 57
13 66 31
-26 15 38
91 95 -29
24 10 41
-65 4 68
-23 -41 24
-91 68 -56
-21 -30 75
53 -68 -14
55 -15 -16
56 -92 46
-35 -81 -86
-38 20 25
63 -73 87
-62 19 20
10 62 44
91 -97 -20
30 8...

output:

14562.176257060317

result:

ok found '14562.1762571', expected '14562.1762571', error '0.0000000'

Test #17:

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

input:

100 50
44 10 -8
65 51 8
-33 -18 83
-10 0 -35
49 41 71
97 50 -35
5 16 -51
-88 54 84
-51 -38 27
-81 -54 75
-23 32 0
42 -74 13
3 46 6
17 -21 -5
-26 -84 26
-72 -29 58
-87 -57 42
14 -17 73
80 -79 31
-79 -33 -34
-35 -77 -12
4 -39 63
-90 4 -93
-51 -66 55
-15 48 -47
58 -34 61
-75 30 -37
54 48 -97
-39 -65 -2...

output:

3709.671025193868

result:

ok found '3709.6710252', expected '3709.6710252', error '0.0000000'

Test #18:

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

input:

100 50
75 -15 76
-88 -42 -82
-65 61 63
-67 85 58
-39 0 -82
-50 -68 -82
-14 -70 32
-46 -39 21
-40 -96 21
-50 -28 86
-56 -30 -14
-31 -43 -47
49 45 39
94 -78 23
-64 98 38
47 50 -97
62 -84 -1
1 6 -1
-13 -34 3
-55 -49 -38
-8 53 39
-96 56 90
-100 -66 50
-15 -94 68
-55 -98 -86
-99 -84 99
-93 -8 17
-72 -7 8...

output:

9554.846640424541

result:

ok found '9554.8466404', expected '9554.8466404', error '0.0000000'

Test #19:

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

input:

100 50
-94 86 -16
-41 91 28
3 -61 -82
2 -31 51
49 -66 -35
4 -11 -29
95 85 -78
23 10 0
-3 -45 -82
65 -4 -75
67 15 -87
100 47 52
-90 -16 17
97 -77 93
-28 30 47
92 4 -38
-38 88 80
-5 15 -71
7 -25 -81
-91 -62 -76
37 27 -79
1 92 22
-25 -25 -31
21 90 15
29 88 12
-53 62 -58
-67 67 -49
30 60 53
-52 -66 -12
...

output:

8547.280268488899

result:

ok found '8547.2802685', expected '8547.2802685', error '0.0000000'

Test #20:

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

input:

100 50
12 61 69
-94 -76 -63
-55 94 100
-55 79 -32
-40 94 13
33 47 -77
52 94 59
40 88 -54
-91 14 52
-50 -29 2
-14 -31 -42
-72 7 34
-62 -84 85
23 7 -8
-4 -64 57
60 -30 52
99 72 -27
-1 -70 -43
-68 -74 -24
79 -27 4
-77 66 -75
-51 -56 39
-80 -65 62
33 4 46
-24 8 79
-33 -66 8
49 35 71
93 4 -23
-20 -15 30
...

output:

23066.081492891535

result:

ok found '23066.0814929', expected '23066.0814929', error '0.0000000'

Test #21:

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

input:

100 50
44 36 53
54 57 47
-88 -29 80
15 -37 61
48 -73 -40
-13 29 -48
-91 -21 96
57 66 17
46 73 85
11 21 -23
80 98 1
57 -33 91
93 23 -48
-50 67 -10
46 43 -33
54 12 -58
10 32 -9
2 -30 86
-67 -98 -93
22 -92 84
-66 -96 -71
-2 22 56
-35 -80 55
-81 -81 76
-2 28 -30
-89 82 49
66 -97 15
-70 -27 -99
-89 -90 -...

output:

3168.558655251171

result:

ok found '3168.5586553', expected '3168.5586553', error '0.0000000'

Test #22:

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

input:

100 50
75 -64 61
1 -10 -43
-21 -50 -40
59 73 -47
-41 87 7
16 87 -95
41 -37 32
75 45 -39
-17 -68 -56
-3 -4 53
75 -49 46
86 27 -28
-79 55 96
-23 -49 -86
95 50 -48
23 -21 -43
47 16 -91
-94 -14 14
-66 -20 -35
-9 -57 -37
20 -56 -67
46 75 73
86 -94 -52
5 -66 6
20 -52 37
-70 -71 91
-19 72 -66
69 18 26
42 6...

output:

6342.363872994109

result:

ok found '6342.3638730', expected '6342.3638730', error '0.0000000'

Test #23:

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

input:

100 50
82 -89 45
49 23 92
-53 -71 -60
-73 -43 46
47 -79 -46
70 -57 58
98 48 68
-33 23 -93
95 -9 78
82 72 29
95 81 91
39 -12 55
75 -14 -37
-96 10 12
-56 -44 63
17 -56 -54
83 -25 28
-91 -99 -58
61 -69 97
-66 -22 -82
-95 7 63
95 -48 15
-70 -9 -59
-8 74 -65
-57 69 4
-25 -98 31
97 64 79
32 -38 50
-27 10 ...

output:

5068.374553841857

result:

ok found '5068.3745538', expected '5068.3745538', error '0.0000000'

Test #24:

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

input:

100 50
37 76 60
-84 -10 66
-69 64 -95
35 -92 2
78 -64 76
43 -40 -40
69 73 -27
-20 2 -25
-17 -41 64
-6 45 22
61 8 2
-2 28 -33
59 -53 -10
46 -9 13
17 -48 -14
-18 -75 95
-43 -72 -67
17 -86 -68
95 -80 49
-73 -34 -51
64 -98 13
61 -43 11
-70 -54 61
-13 -47 -88
20 65 -76
-65 -90 89
16 -48 -73
-39 72 64
91 ...

output:

5608.177883918240

result:

ok found '5608.1778839', expected '5608.1778839', error '0.0000000'

Test #25:

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

input:

100 50
2371 -2182 4649
-7045 1625 6370
105 7051 -9889
8094 -378 -5091
3473 1211 776
305 -1104 3821
-6004 -3747 3096
-2940 3883 -2452
4468 8364 7278
-6246 -6010 3529
-1593 -2340 -2959
-4650 3229 -7593
2254 -2797 -7043
-5324 440 -6424
3915 1603 8567
-8255 -1989 -172
-178 6139 -2212
2046 -5614 1102
876...

output:

27472.060887955427

result:

ok found '27472.0608880', expected '27472.0608880', error '0.0000000'

Test #26:

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

input:

100 50
7295 -7151 8895
2840 -7771 4287
9596 629 7734
4640 4998 -2724
-7303 3508 -8632
5689 5745 -3696
-2324 2551 736
-279 5065 -9364
-6120 6689 2325
6218 -3971 9553
9311 6964 6866
-5681 -6294 -8546
3295 9711 3890
-2597 -7660 6808
3862 -5304 8925
-652 8281 829
1161 -3429 3647
-9674 3712 -8684
9818 79...

output:

17411.293822742751

result:

ok found '17411.2938227', expected '17411.2938227', error '0.0000000'

Test #27:

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

input:

100 50
1920 -9858 582
5283 2833 9645
1346 -5793 175
-1670 -9627 9347
6507 5806 -2624
-8927 5151 8787
8798 4263 636
9824 6248 8906
3294 7275 7671
-8760 5510 8136
9917 3708 4131
-6712 -8374 -7238
7193 -5224 2265
9832 6503 -9665
-3633 -9950 7022
6950 3666 1830
-2086 -438 2063
-8836 5596 6712
-1688 -528...

output:

14706.563250841416

result:

ok found '14706.5632508', expected '14706.5632508', error '0.0000000'

Test #28:

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

input:

100 50
-598 -9710 -2614
7727 -6564 120
539 -4773 -9645
2318 -4251 6597
-9387 -4456 528
9016 -2884 1269
2180 5975 536
-74 -2867 1995
5265 5600 2718
6560 7550 -3579
820 -6989 8839
-302 4961 -3074
8234 -9861 -6803
2261 -1596 3567
8873 -7154 -5179
1994 3638 -6871
-746 -2564 480
-555 7480 -5335
-2896 144...

output:

17290.181526015695

result:

ok found '17290.1815260', expected '17290.1815260', error '0.0000000'

Test #29:

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

input:

100 50
4326 5322 9074
-2389 4041 5478
-268 8807 2798
-3992 -9173 -1333
-3019 5283 -3762
-3339 6821 4049
-6698 -4872 -9267
2587 -1684 -7178
4975 3925 -9677
-977 -2970 -4996
-8276 2315 -1337
-8775 2880 5675
-7869 2647 -6168
4988 2863 -3202
8820 8201 -7083
-7548 -976 1572
5710 427 6338
284 9364 -7679
-...

output:

16111.661143897069

result:

ok found '16111.6611439', expected '16111.6611439', error '0.0000000'

Test #30:

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

input:

100 50
-8490 2615 -6681
55 -5356 -6308
-1076 5241 -7022
-4 -3797 1034
1089 -4979 9687
2045 -6331 -3468
-3018 -3160 5518
-7311 -3357 -6647
-5613 -8048 3111
-8514 -8373 1029
-7670 1321 -4071
491 -6642 -2720
-6828 -4846 -7793
-2584 -5236 -9972
1325 1294 717
7496 9294 5429
-2654 1157 4754
8565 8392 -716...

output:

7217.032702502401

result:

ok found '7217.0327025', expected '7217.0327025', error '0.0000000'

Test #31:

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

input:

100 50
3876 -9796 -9877
2498 5248 -8391
973 6261 5420
-3458 9021 3402
7457 -2682 5397
-12 -6925 9015
8104 -1448 5418
2793 -9616 -6117
3801 2837 -1842
6806 1109 7053
3234 -9377 5754
6902 1576 -1412
6773 -7222 3140
143 -8219 3260
-6170 4090 -1186
-4902 1824 -6129
-8756 4148 910
-3155 -9725 -9511
-1997...

output:

9104.550466250830

result:

ok found '9104.5504663', expected '9104.5504663', error '0.0000000'

Test #32:

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

input:

100 50
8800 7497 -8487
4942 -4149 -3033
166 -161 -4400
-2326 -5604 2913
-8437 -385 1107
7633 2780 1497
-775 7706 5318
5454 -8433 4711
5772 -1694 -3938
-731 3148 -4662
3840 7369 -7278
5870 -7946 -2365
-1889 -4417 -5927
-7428 5944 -3510
-6223 -556 6613
-4741 4651 7432
-4561 -5420 -674
7386 -7841 5885
...

output:

30857.605318652342

result:

ok found '30857.6053187', expected '30857.6053187', error '0.0000000'

Test #33:

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

input:

100 50
-4017 2529 -4241
2268 6456 -5116
-8084 -6582 -4516
-5780 -228 -7278
-2069 9354 -5444
5576 2187 -3164
-7393 -3141 -4485
2998 9895 -2200
7743 -3369 -8891
4291 -7372 -6079
-5257 9231 -2570
-2603 2532 -8499
-847 8091 -7553
-7557 -2155 2280
6283 2240 4710
-9697 7479 6172
-3222 5013 -2258
8225 -595...

output:

15176.391148249131

result:

ok found '15176.3911482', expected '15176.3911482', error '0.0000000'

Test #34:

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

input:

100 50
8754 888 -381
-3542 4310 -2292
-1678 -1041 -8367
-4583 -280 -2144
4349 -6430 -3203
-6746 1427 -2288
-5786 -605 3073
-4280 -8381 1800
4489 4959 -4128
8166 -9421 540
-7865 -2658 -1186
-1960 -6268 -1822
-6780 -3314 -8672
-9551 9512 7396
-5115 552 659
9107 -3752 -4072
2847 -6362 -8203
2639 9837 2...

output:

5686.291302671647

result:

ok found '5686.2913027', expected '5686.2913027', error '0.0000000'

Test #35:

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

input:

5000 50
5700 7391 -765
6182 955 4789
2738 3522 -9511
-9375 8053 6271
7210 -4184 5024
-6202 7822 5607
-4541 6422 -3391
-3883 -5790 -8937
9452 -9034 -8442
-3437 -9430 6958
-1807 7162 7510
-8508 1073 4353
-2025 -6727 -6673
7638 -2409 -3032
-4418 -2971 7057
-4730 -3181 9300
3262 -6125 5994
-9459 -3396 3...

output:

38569741.685099132359

result:

ok found '38569741.6850991', expected '38569741.6850991', error '0.0000000'

Test #36:

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

input:

5000 50
-6116 -6942 -5183
-9931 440 -7353
9096 -9737 -370
-6353 -3747 2157
-9089 763 7237
-2700 -1190 -9533
168 6399 47
2641 4718 8573
9428 -805 -9795
-846 -7008 -4909
-9878 -4863 632
-5862 3295 -867
79 3495 -6449
-8160 -9763 -9564
-3826 -5342 -752
457 -8157 8392
3571 -386 4952
-9756 -1075 -6942
-38...

output:

32054994.080926571041

result:

ok found '32054994.0809266', expected '32054994.0809266', error '0.0000000'

Test #37:

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

input:

5000 50
7185 6167 2959
-6042 -75 -1755
-1692 -734 8770
-475 -2989 -1957
4317 -3993 9450
8243 9798 -2411
2616 -6184 6341
-7981 -9360 -4215
-3154 -5136 8853
4601 -4586 7810
4908 -7185 -9103
-7802 -9897 -1501
2184 8537 1217
-9074 2884 -5797
-6090 -271 -1119
2787 9723 -2219
-6419 -4945 1053
-7196 1246 7...

output:

22807058.402091726661

result:

ok found '22807058.4020917', expected '22807058.4020917', error '0.0000000'

Test #38:

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

input:

5000 50
-4631 1537 8244
-5010 9709 6104
79 6008 -2091
285 -7347 1371
8020 8396 4221
-814 786 2450
7324 -3946 75
5985 -8555 -6706
9381 3093 57
-2511 -4425 5645
1953 790 -6279
7404 -233 -9577
-3154 1019 1440
-7727 -6731 7673
-8355 -2642 8217
-2324 4747 -3127
-6110 794 10
-51 3566 -3595
-7346 1001 7597...

output:

12844986.777912668884

result:

ok found '12844986.7779127', expected '12844986.7779127', error '0.0000000'

Test #39:

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

input:

5000 50
8671 -5354 3826
-1122 9194 -3182
9292 5308 -393
-4135 -6588 6961
1424 3640 6434
-7610 -5371 -131
2330 3472 -6190
5066 7071 506
-3201 -1238 9002
-7362 -2004 -9078
-3262 -6649 -5716
-4834 -867 2347
-8491 -3643 9106
-3524 5916 -1120
-321 2429 409
2863 2627 6263
-3541 6533 8670
-347 5887 -1921
-...

output:

34389828.764920994639

result:

ok found '34389828.7649210', expected '34389828.7649210', error '0.0000000'

Test #40:

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

input:

5000 50
9413 -2542 9112
2767 1237 -5026
-1495 1753 8747
9185 9054 2847
5127 6326 -3912
-4109 5617 4730
-5520 3449 7546
-5555 7876 -1984
-3225 6991 206
5527 -7024 3641
1226 1327 4551
-2187 8798 1713
-6387 8841 -3229
8121 -1438 2647
9974 58 9745
-2249 -2349 -4348
6471 -5468 185
2212 8207 9455
1731 -80...

output:

30491514.423866085708

result:

ok found '30491514.4238661', expected '30491514.4238661', error '0.0000000'

Test #41:

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

input:

5000 50
-2403 3125 4694
6655 3578 2833
-2580 1053 -2114
4764 9813 -1267
-8910 -1286 562
6835 4047 9591
9487 3425 1281
8410 -6202 -9656
-3248 2660 -8589
-9027 2840 -8227
-3989 -996 -9770
3315 -4395 -3507
8277 -6119 9554
-234 -8792 -3885
7710 5129 1936
7524 2972 -5256
6779 271 -858
1915 3086 -8873
-62...

output:

21029309.692938566208

result:

ok found '21029309.6929386', expected '21029309.6929386', error '0.0000000'

Test #42:

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

input:

5000 50
-9102 5937 9979
-2015 3064 8431
-5926 7795 -3272
-1917 5455 2061
-5208 -6041 2775
-2223 -4966 7010
9078 -6897 -4984
7492 4306 -2443
-5533 8033 356
-6436 5262 4492
498 -3318 496
-8923 7530 -4141
-9620 -3339 -2781
-8590 -8704 -118
-4257 2758 3830
2413 -9446 4134
-3210 -4288 7803
-5823 -7153 24...

output:

15405928.875117853284

result:

ok found '15405928.8751179', expected '15405928.8751179', error '0.0000000'

Test #43:

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

input:

5000 50
8785 -8396 5562
1873 2549 -3711
3287 9356 5868
1105 6213 7651
8198 -3355 -7571
3540 -1420 -8130
4084 522 8751
4312 -2331 -4934
-5557 -3740 -998
-989 7683 9770
-4717 4658 3321
6283 4636 -4775
5044 9145 -2557
3055 -3499 -6650
-6521 7829 3463
7599 -4124 -4216
9657 1451 -5799
4178 7727 -5526
-97...

output:

25049192.867981396616

result:

ok found '25049192.8679814', expected '25049192.8679814', error '0.0000000'

Test #44:

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

input:

5000 50
-8659 -367 9256
-9844 -2373 3813
-4517 -9608 -4052
-834 8836 4141
-1746 1316 -6769
7685 3834 -4221
-5187 -9190 4411
-6739 4996 -1483
-376 132 -7570
-4867 -2037 -8354
8053 -9958 -6371
-8120 -1516 -323
-7072 1724 1032
-6926 -2715 -6839
-8533 1769 4059
496 9766 -8389
3303 -7413 1434
-4932 -3279...

output:

34007643.007585346699

result:

ok found '34007643.0075853', expected '34007643.0075853', error '0.0000000'

Test #45:

score: 0
Accepted
time: 491ms
memory: 60244kb

input:

200000 50
-9392 -1129 5331
-3946 7566 -4786
1183 3453 2453
-9135 -656 5601
1997 -6870 -7600
3356 8277 625
3122 336 -5593
7915 -3706 5803
6368 4352 -2915
-6409 -7806 5258
-7127 9826 -7748
6449 -107 -899
2256 4705 -5370
8915 -520 5453
7286 4625 -8148
-3985 2129 8398
6114 1653 3975
-7019 -3757 6743
-23...

output:

685910361.939351797104

result:

ok found '685910361.9393518', expected '685910361.9393518', error '0.0000000'

Test #46:

score: 0
Accepted
time: 518ms
memory: 59944kb

input:

200000 50
3717 -5547 9220
-4460 5722 4427
483 -7408 8331
-8376 4933 -994
4683 -4657 -4098
-2801 5696 -7225
-7200 -5929 3786
1278 -3936 5779
-8261 -4444 9974
-3987 -2529 9746
848 92 7458
-3888 -8183 -6237
2180 -7630 -6283
1561 -9313 3189
-7643 -3184 -5817
3597 4077 -1592
-8148 -9688 -3763
7860 -4940 ...

output:

726192406.563762426376

result:

ok found '726192406.5637624', expected '726192406.5637624', error '0.0000000'

Test #47:

score: 0
Accepted
time: 497ms
memory: 60404kb

input:

200000 50
-913 -9964 549
5323 3878 -4100
7225 -5710 -8649
7266 8261 2709
9630 4998 9106
8187 3115 7781
219 -2491 2868
2084 3277 5756
-32 -5797 5123
5877 2748 4530
-1474 5772 -4780
2920 -8817 -4132
-2482 5153 -2080
4505 4157 3781
9987 6153 -631
8919 -9390 978
-9851 9270 6238
-9820 9293 3261
-3926 669...

output:

801487345.437529206276

result:

ok found '801487345.4375292', expected '801487345.4375292', error '0.0000000'

Test #48:

score: 0
Accepted
time: 497ms
memory: 61112kb

input:

200000 50
4755 -4679 4437
4808 -8264 5114
-3773 -6868 4671
8025 -3294 8672
-7685 -232 49
-825 -2322 -7511
-7247 -8756 -3168
-2292 -6656 -6827
-4363 3147 -1989
8298 8026 9018
-6057 -3963 8164
2287 -4335 -9470
-9999 -7182 9565
-2849 7923 1517
-4943 -1656 -5742
-3499 -7442 1286
5591 -2071 5942
-7500 -1...

output:

841632353.848273873329

result:

ok found '841632353.8482739', expected '841632353.8482739', error '0.0000000'

Test #49:

score: 0
Accepted
time: 524ms
memory: 62120kb

input:

200000 50
7566 -9097 8326
4294 2451 -5674
2969 2272 7693
-3775 34 -7626
-4999 1981 3551
-9838 -4903 -5063
171 -2463 6212
-1487 556 -6851
-8693 -5648 -6840
3278 3600 3803
-8380 -3399 -4073
-8050 -4969 -7365
2484 483 -6233
-2761 -8311 -747
-7314 7680 -3411
1823 -8350 3856
-8671 -3114 -1797
-5179 80 -2...

output:

846720759.614533424377

result:

ok found '846720759.6145334', expected '846720759.6145334', error '0.0000000'

Test #50:

score: 0
Accepted
time: 514ms
memory: 60576kb

input:

200000 50
-6767 -3811 -7787
-5924 -2249 3539
2269 3970 -6431
4425 -4080 5780
-51 4194 -5507
-6292 -42 -354
9851 -8728 176
-8123 -1934 5685
-465 5558 6049
-4003 -3682 848
-404 -575 -8869
-1242 4695 7299
-2178 707 5412
2444 -7400 7287
-2243 7313 1775
4288 8482 4164
6772 -4156 -4354
9701 1754 4318
-379...

output:

952846481.452487468719

result:

ok found '952846481.4524875', expected '952846481.4524875', error '0.0000000'

Test #51:

score: 0
Accepted
time: 508ms
memory: 60712kb

input:

200000 50
8604 -8229 3543
6120 -4093 193
-1287 551 -3409
5184 8951 9482
2635 6407 7698
4697 4819 4354
-2732 5008 9556
-5057 5278 3400
-4795 -5499 -8505
5861 -5846 -4367
-2727 9691 6337
981 9178 9403
-9695 931 -5800
-4910 -3634 5022
-4614 -496 4106
2168 132 -5825
-7490 4504 7908
-538 -6871 -3703
-205...

output:

930555767.898788094521

result:

ok found '930555767.8987881', expected '930555767.8987881', error '0.0000000'

Test #52:

score: 0
Accepted
time: 505ms
memory: 59524kb

input:

200000 50
1713 -2943 7432
5605 -5937 -891
-9429 2249 2469
826 -2604 2887
-4977 8620 -8802
3126 2238 6802
9804 -1257 -3922
8308 -7510 3377
3433 -6852 6645
8282 6873 121
-7310 2813 4397
7789 8544 4066
-4654 1155 -1597
7737 9836 -4684
457 1398 -1005
-2808 -3037 -5517
7952 3461 7612
-5659 -5198 836
-542...

output:

867511792.595178127289

result:

ok found '867511792.5951781', expected '867511792.5951782', error '0.0000000'

Test #53:

score: 0
Accepted
time: 511ms
memory: 59332kb

input:

200000 50
-2918 -7361 1022
7947 1922 8322
-2687 -1169 -7069
1584 -6718 6589
-9733 -6907 2142
4411 -343 -8490
6924 -7522 2602
-8627 10000 3353
-897 4353 -467
-9297 4708 -5094
-9632 -6922 7043
-2548 -6974 6170
5568 8821 -9952
-9320 -6399 3350
-1914 1032 -8378
-7784 8614 4495
-6310 -7880 -2388
4103 391...

output:

978924220.152041673660

result:

ok found '978924220.1520417', expected '978924220.1520417', error '0.0000000'

Test #54:

score: 0
Accepted
time: 508ms
memory: 61112kb

input:

200000 50
2851 -3667 9306
-9534 -3113 517
-9092 -8828 -9007
-8352 6918 -3354
-5062 8780 6287
-633 -8993 -21
-5049 8138 4110
6142 6009 8534
-4468 5223 -4345
984 -5974 7676
8313 8504 5200
-1257 4920 6613
409 -7591 -9635
-1093 -4327 1338
-533 1628 4520
-3597 -5263 -9301
7683 9652 8503
-1786 4506 8027
-...

output:

774758696.455128669739

result:

ok found '774758696.4551287', expected '774758696.4551287', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed