QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#452457#7568. KeychainpandapythonerAC ✓6519ms8000kbC++2011.9kb2024-06-23 19:01:512024-06-23 19:01:51

Judging History

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

  • [2024-06-23 19:01:51]
  • 评测
  • 测评结果:AC
  • 用时:6519ms
  • 内存:8000kb
  • [2024-06-23 19:01:51]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;

#define lll __int128_t
#define ll __int128_t
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)

const ll inf = 1e18;
mt19937 rnd(234);
const flt eps = 1e-7;


struct vec {
    ll x, y;

    vec() : x(0), y(0) {}
    vec(ll x, ll y) : x(x), y(y) {}

    ll len2() const {
        return x * x + y * y;
    }


    flt len() const {
        return sqrt((flt)len2());
    }


    vec rotate90() {
        return vec(-y, x);
    }
};


vec operator+(const vec& a, const vec& b) {
    return vec(a.x + b.x, a.y + b.y);
}

vec operator-(const vec& a, const vec& b) {
    return vec(a.x - b.x, a.y - b.y);
}


vec operator/(const vec& a, ll k) {
    return vec(a.x / k, a.y / k);
}


vec operator*(const vec& a, ll k) {
    return vec(a.x * k, a.y * k);
}


ll operator*(const vec& a, const vec& b) {
    return a.x * b.x + a.y * b.y;
}


ll operator%(const vec& a, const vec& b) {
    return a.x * b.y - a.y * b.x;
}


int get_type(const vec& a) {
    if (a.x == 0 and a.y == 0) {
        return 0;
    }
    if (a.x > 0) {
        return 1;
    }
    if (a.x < 0) {
        return 3;
    }
    if (a.y > 0) {
        return 2;
    }
    if (a.y < 0) {
        return 4;
    }
    assert(0);
}


bool operator<(const vec& a, const vec& b) {
    int ta = get_type(a);
    int tb = get_type(b);
    if (ta != tb) {
        return ta < tb;
    }
    return a % b > 0;
}


ll div_ceil(ll a, ll b) {
    if (a >= 0) {
        return (a + b - 1) / b;
    }
    return a / b;
}


struct line {
    vec a;
    ll c;

    line() {}
    line(ll a, ll b, ll c) : a(a, b), c(c) {}
    line(const vec& a, ll c) : a(a), c(c) {}
    line(const vec& p, const vec& q) {
        assert((p - q).len2() > eps);
        a = (p - q).rotate90();
        c = a * p;
    }


    ll get(const vec& p) {
        return a * p - c;
    }

    bool strict_contains(const array<ll, 3>& p) {
        auto [x, y, z] = p;
        ll val = x * a.x + y * a.y;
        // now we need to check that val / z - c > 0 <=>
        // <=> val / z > c <=> ceil(val / z) > c
        return div_ceil(val, z) > c;
    }

    flt normc() {
        return (flt)c / a.len();
    }
};


bool operator<(const line& a, const line& b) {
    return a.a < b.a;
}


array<ll, 3> intersect(const line& s, const line& t) {
    array<ll, 3> p;
    p[2] = s.a.x * t.a.y - s.a.y * t.a.x;
    assert(p[2] != 0);
    p[0] = s.c * t.a.y - s.a.y * t.c;
    p[1] = s.a.x * t.c - s.c * t.a.x;
    if (p[2] < 0) {
        p[0] *= -1;
        p[1] *= -1;
        p[2] *= -1;
    }
    return p;
}


namespace opt {
    flt opt_r = 1e20;

    char opt_type = '0';

    line ln;

    array<ll, 3> cc;
    flt cr;

    void opt_circle(const array<ll, 3>& mcc, flt mcr, flt r) {
        if (r < opt_r) {
            opt_r = r;
            opt_type = 'C';
            cc = mcc;
            cr = mcr;
        }
    }


    void opt_line(const line& mln, flt r) {
        if (r < opt_r) {
            opt_r = r;
            opt_type = 'L';
            ln = mln;
        }
    }


    void print() {
        cout << fixed << setprecision(20);
        if (opt_type == 'C') {
            cout << opt_r << "\n";
            cout << 'C' << " " << (long long)cc[0] << " " << (long long)cc[1] << " " << (long long)cc[2] << " " << cr << "\n";
            return;
        }
        if (opt_type == 'L') {
            cout << opt_r << "\n";
            cout << 'L' << " " << (long long)ln.a.x << " " << (long long)ln.a.y << " " << (long long)ln.c << "\n";
            return;
        }
        assert(0);
    }
};


line bisector(const vec& a, const vec& b) {
    vec d = a - b;
    ll c = d * a + d * b;
    ll f = 2 * (d * a) - c;
    assert(f > 0);
    if (c % 2 == 0) {
        return line(d, c / 2);
    }
    return line(vec(d.x * 2, d.y * 2), c);
}


flt dist2(const vec& a, const array<ll, 3>& b) {
    flt dx = (a.x - (flt)(b[0]) / b[2]);
    flt dy = (a.y - (flt)(b[1]) / b[2]);
    return dx * dx + dy * dy;
}


flt dist(const vec& a, const array<ll, 3>& b) {
    return sqrt(dist2(a, b));
}


int n;
vector<vec> a;
vector<vec> hull;


void build_hull() {
    auto s = a;
    int j = 0;
    for (int i = 1; i < n; i += 1) {
        if (s[i].x < s[j].x or (s[i].x == s[j].x and s[i].y < s[j].y)) {
            j = i;
        }
    }
    swap(s[0], s[j]);
    sort(s.begin() + 1, s.end(), [&](const vec& p, const vec& q) {
        ll biba = (p - s[0]) % (q - s[0]);
        if (biba != 0) {
            return biba > 0;
        }
        return (p - s[0]).len2() < (q - s[0]).len2();
        });
    hull = { s[0] };
    for (int i = 1; i < n; i += 1) {
        auto v = s[i];
        while ((int)hull.size() >= 2 and
            (hull.back() - hull[(int)hull.size() - 2]) % (v - hull[(int)hull.size() - 2]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(v);
    }
}


void solve_lines() {
    assert((int)hull.size() > 0);
    if ((int)hull.size() == 1) {
        auto v = hull[0];
        opt::opt_line(line(v, v * v), 0);
        return;
    }
    int m = (int)hull.size();
    for (int i = 0; i < m; i += 1) {
        auto v = (hull[(i + 1) % m] - hull[i]).rotate90();
        int l = 0;
        int r = (n - 1);
        while (r - l > 4) {
            int m1 = (2 * l + r) / 3;
            int m2 = (l + 2 * r) / 3;
            if (v * (hull[(i + 1 + m1) % m] - hull[i]) > v * (hull[(i + 1 + m2) % m] - hull[i])) {
                r = m2;
            } else {
                l = m1;
            }
        }
        vec f = hull[i];
        for (int j = l; j <= r; j += 1) {
            auto t = hull[(i + 1 + j) % m];
            if ((f - hull[i]) * v < (t - hull[i]) * v) {
                f = t;
            }
        }
        ll c = hull[i] * v + f * v;
        line ln;
        if (c % 2 == 0) {
            ln = line(v, c / 2);
        } else {
            ln = line(vec(v.x * 2, v.y * 2), c);
        }
        flt rad = ((f - hull[i]) * v) / v.len() / 2;
        opt::opt_line(ln, rad);
    }
}


pair<flt, flt> try_point(const array<ll, 3>& u) {
    flt mx = 0;
    flt mn = 1e20;
    for (auto v : a) {
        flt d = dist2(v, u);
        mx = max(mx, d);
        mn = min(mn, d);
    }
    mx = sqrt(mx);
    mn = sqrt(mn);
    opt::opt_circle(u, (mx + mn) / 2, (mx - mn) / 2);
    return { mn, mx };
}


void solve_circles_slow() {
    vector<line> lines;
    for (int i = 0; i < n; i += 1) {
        for (int j = i + 1; j < n; j += 1) {
            lines.push_back(bisector(a[i], a[j]));
        }
    }
    for (int i = 0; i < (int)lines.size(); i += 1) {
        for (int j = i + 1; j < (int)lines.size(); j += 1) {
            auto lni = lines[i];
            auto lnj = lines[j];
            if (lni.a % lnj.a != 0) {
                auto u = intersect(lni, lnj);
                try_point(u);
            }
        }
    }
}


deque<line> intersect_halfplanes(const vector<line>& _lns) {
    vector<line> nlns = { line(vec(1, 0), -1e11),
                            line(vec(0, 1), -1e11),
                            line(vec(-1, 0), -1e11),
                            line(vec(0, -1), -1e11) };
    vector<line> lns((int)_lns.size() + 4);
    merge(all(_lns), all(nlns), lns.begin());
    // sort(all(lns));
    deque<line> d;
    for (auto ln : lns) {
        if (!d.empty() and d.back().a % ln.a == 0) {
            assert(d.back().a * ln.a > 0);
            if (d.back().normc() > ln.normc()) {
                continue;
            } else {
                d.pop_back();
            }
        }
        while ((int)d.size() >= 2 and !ln.strict_contains(intersect(d.back(), d[(int)d.size() - 2]))) {
            d.pop_back();
        }
        d.push_back(ln);
    }
    while ((int)d.size() >= 3) {
        if (!d.back().strict_contains(intersect(d[0], d[1]))) {
            d.pop_front();
            continue;
        }
        if (!d[0].strict_contains(intersect(d.back(), d[(int)d.size() - 2]))) {
            d.pop_back();
            continue;
        }
        if ((int)d.size() >= 4) {
            if (!d[(int)d.size() - 2].strict_contains(intersect(d[0], d[1]))) {
                d.pop_front();
                continue;
            }
            if (!d[1].strict_contains(intersect(d.back(), d[(int)d.size() - 2]))) {
                d.pop_back();
                continue;
            }
        }
        break;
    }
    assert((int)d.size() >= 3);
    return d;
}


vector<deque<line>> nearest, furthest;


void build_nearest() {
    nearest.resize(n);
    for (int i = 0; i < n; i += 1) {
        vector<vec> b = a;
        b.erase(b.begin() + i);
        sort(all(b), [&](const vec& p, const vec& q) {
            return (a[i] - p) < (a[i] - q);
            });
        vector<line> lns;
        lns.reserve(n - 1);
        for (auto v : b) {
            lns.push_back(bisector(a[i], v));
        }
        nearest[i] = intersect_halfplanes(lns);
    }
}


void build_furthest() {
    int m = (int)hull.size();
    furthest.resize(m);
    for (int i = 0; i < m; i += 1) {
        vector<vec> b = hull;
        b.erase(b.begin() + i);
        rotate(b.begin(), b.begin() + i, b.end());
        vector<line> lns;
        lns.reserve(m - 1);
        for (auto v : b) {
            lns.push_back(bisector(v, hull[i]));
        }
        int mn = 0;
        for (int j = 1; j < (int)lns.size(); j += 1) {
            if (lns[j] < lns[mn]) {
                mn = j;
            }
        }
        rotate(lns.begin(), lns.begin() + mn, lns.end());
        furthest[i] = intersect_halfplanes(lns);
    }
}





void solve_circles() {
    build_nearest();
    build_furthest();
    for (auto& lns : nearest) {
        for (int i = 0; i < (int)lns.size(); i += 1) {
            int j = (i + 1) % (int)lns.size();
            auto v = intersect(lns[i], lns[j]);
            try_point(v);
        }
    }
    for (auto& lns : furthest) {
        for (int i = 0; i < (int)lns.size(); i += 1) {
            int j = (i + 1) % (int)lns.size();
            auto v = intersect(lns[i], lns[j]);
            try_point(v);
        }
    }
    int m = (int)hull.size();
    rep(s, n) rep(t, m) {
        auto& lnss = nearest[s];
        auto& lnst = furthest[t];
        rep(i, (int)lnss.size()) rep(j, (int)lnst.size()) {
            if (lnss[i].a % lnst[j].a == 0) {
                continue;
            }
            int pi = (i + (int)lnss.size() - 1) % (int)lnss.size();
            int ni = (i + 1) % (int)lnss.size();
            int pj = (j + (int)lnst.size() - 1) % (int)lnst.size();
            int nj = (j + 1) % (int)lnst.size();
            auto v = intersect(lnss[i], lnst[j]);
            if (lnss[pi].strict_contains(v) and
                lnss[ni].strict_contains(v) and
                lnst[pj].strict_contains(v) and
                lnst[nj].strict_contains(v)) {
                flt mn = dist(a[s], v);
                flt mx = dist(hull[t], v);
                opt::opt_circle(v, (mx + mn) / 2, (mx - mn) / 2);
            }
        }
    }
}


void solve() {
    build_hull();
    solve_lines();
    solve_circles();
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        long long x, y;
        cin >> x >> y;
        a[i] = vec(x, y);
    }
    solve();
    opt::print();
    return 0;
}

/*
4
2 1
1 3
2 4
7 2


7
26919 7739
85584 91359
47712 21058
13729 26355
16636 96528
88747 93023
46770 1150

10
756 624
252 208
504 416
378 312
203 287
329 391
0 0
707 703
126 104
581 599


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2 1
1 3
2 4
7 2

output:

0.27069063257455483473
C 288 180 72 2.77069063257455461269

result:

ok jury ans = 0.270690633, participant ans = 0.270690633

Test #2:

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

input:

7
26919 7739
85584 91359
47712 21058
13729 26355
16636 96528
88747 93023
46770 1150

output:

9663.87959749101719353348
C 225348605048152 367109733895066 6023049538 50864.33205303458089474589

result:

ok jury ans = 9663.879597491, participant ans = 9663.879597491

Test #3:

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

input:

10
756 624
252 208
504 416
378 312
203 287
329 391
0 0
707 703
126 104
581 599

output:

46.05915288207108204688
L -624 756 45150

result:

ok jury ans = 46.059152882, participant ans = 46.059152882

Test #4:

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

input:

1
15782 63130

output:

0.00000000000000000000
L 15782 63130 4234468424

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #5:

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

input:

2
94217 66974
75089 40029

output:

0.00000000000000000000
L -26945 19128 -1257598393

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #6:

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

input:

3
48303 6057
77370 21547
87988 74434

output:

0.00000000000363797881
C 109980206721647 155256378115679 2745587218 51159.51784632558701559901

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #7:

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

input:

4
91497 34248
20062 67825
81300 76644
27657 65928

output:

3533.57135836280576768331
C 276103424580480 206123542753440 5006049600 40530.85328799497801810503

result:

ok jury ans = 3533.571358363, participant ans = 3533.571358363

Test #8:

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

input:

5
69930 13744
97997 49343
74612 89749
36739 52364
89397 14014

output:

5337.85352978117407474201
C 618235642032675 450340094908105 9189418290 36059.79053590994590194896

result:

ok jury ans = 5337.853529781, participant ans = 5337.853529781

Test #9:

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

input:

6
24017 52829
277 30862
67924 91959
21473 63146
96602 58155
873 44434

output:

9102.82195475681146490388
C 385087733514103 178655356183771 6184976998 54224.44932374260679353029

result:

ok jury ans = 9102.821954757, participant ans = 9102.821954757

Test #10:

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

input:

7
2451 56672
42971 77140
61236 94170
81861 25235
68565 61883
16219 86220
16322 5864

output:

10266.42012148960930062458
C 252700496777650 282294440058782 5890713324 39484.56600524945679353550

result:

ok jury ans = 10266.420121490, participant ans = 10266.420121490

Test #11:

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

input:

8
21297 95757
45252 58658
94961 72033
66596 11671
64876 30371
66805 92765
94633 86321
40385 47610

output:

15105.31926122964432579465
C 465051544188545 452234886264771 6714637102 40637.95127333252457901835

result:

ok jury ans = 15105.319261230, participant ans = 15105.319261230

Test #12:

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

input:

9
99732 23947
23186 80590
12619 74244
75677 73760
36840 74512
6496 34550
8184 26365
6 6454
55215 18208

output:

14885.23167591851051838603
C 1056472294995018 1088942021729010 23745626316 44542.55336448235902935266

result:

ok jury ans = 14885.231675919, participant ans = 14885.231675919

Test #13:

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

input:

10
67694 99307
56012 50355
42446 60253
398 14855
82806 93134
53045 14189
19963 51406
72238 90783
58977 92553
91808 75523

output:

21890.67212274691701168194
C 48293860224471 157269094149141 2072072122 46611.32583190371951786801

result:

ok jury ans = 21890.672122747, participant ans = 21890.672122747

Test #14:

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

input:

50
28303 78635
98527 4836
99469 93880
46037 26886
31814 11072
82640 89089
80483 78420
65817 78003
4325 65401
87358 36627
69197 63160
8603 49295
15942 84649
58111 43187
59748 20332
26719 92486
4108 32640
60387 68724
43155 47327
9591 99815
37905 98234
25483 54545
89447 86614
63335 62433
60686 44416
15...

output:

27130.42756290391844231635
C 208208852697721 201287291063801 3707918566 37991.61989905974041903391

result:

ok jury ans = 27130.427562904, participant ans = 27130.427562904

Test #15:

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

input:

50
86917 20549
60266 58924
3312 36573
27556 20198
9678 20153
69075 96294
48970 53352
72362 91554
44370 89782
21855 61657
57607 89111
87444 40267
39146 58700
27668 65946
45465 14550
28873 59735
15851 10864
2791 66253
20744 34442
28637 44319
1253 6922
16147 51571
72072 39253
78169 46742
22183 97841
22...

output:

28626.39387727045686915517
C 309328046815971 252437996644215 5477616186 39070.20421360549516975880

result:

ok jury ans = 28626.393877270, participant ans = 28626.393877270

Test #16:

score: 0
Accepted
time: 2115ms
memory: 6708kb

input:

3000
92948 78658
99013 65575
62135 58049
73566 5036
62021 41092
18242 18337
69531 93648
48044 47267
90750 98807
54790 73639
70408 13307
68742 82075
21339 47233
75103 97053
10958 13262
52441 39682
55881 21527
36660 9741
10401 25304
66452 74105
21712 20753
6193 73558
64161 45507
38414 99590
87783 9105...

output:

33766.31367490881530102342
C 63547765784982 62595291253638 1273847492 35113.45769972466223407537

result:

ok jury ans = 33766.313674909, participant ans = 33766.313674909

Test #17:

score: 0
Accepted
time: 2079ms
memory: 6348kb

input:

3000
27214 96226
85099 19662
65979 35983
30738 22695
64232 25826
80332 65955
38018 8993
54589 60818
30793 23188
13634 33910
69713 39258
47582 73047
93237 21284
20313 19811
85782 7480
54595 6931
43277 24097
38652 42511
63644 12419
85498 83369
9407 29441
96858 70585
82028 22493
77595 59552
49280 68829...

output:

34199.41245007159886881709
C 20400984169424 21722585217760 421038328 35900.85438338310632389039

result:

ok jury ans = 34199.412450072, participant ans = 34199.412450072

Test #18:

score: 0
Accepted
time: 2070ms
memory: 6756kb

input:

3000
37134 38141
82080 22442
5063 78677
12256 16007
66442 34908
66767 62266
6505 59579
96375 74369
11250 31503
48132 83287
93364 65208
26422 39673
5546 6228
65525 82983
20191 26045
81096 33767
90261 77975
16296 40040
30339 15599
4542 16980
32342 97718
22762 67611
64654 50785
68081 19514
35124 33147
...

output:

34115.50564394110551802441
C 52652368728954 54892518170094 1084663548 35250.46659772858401993290

result:

ok jury ans = 34115.505643941, participant ans = 34115.505643941

Test #19:

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

input:

100
19268 48372
48595 53219
31920 44184
21912 55164
42130 54945
19984 48704
4648 55722
40500 43319
42508 53624
24054 54237
45679 45165
7169 51472
1871 45270
37289 57530
28573 49283
7029 49215
44885 51786
32613 49560
10985 57784
37606 46069
24510 55357
41305 49669
13344 48648
13718 54893
12753 47755
...

output:

7198.70317496964707970619
C 472164776811 6197396390133 11182134 503708.25681789586087688804

result:

ok jury ans = 7198.703174970, participant ans = 7198.703174970

Test #20:

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

input:

100
57704 46888
86842 42687
85439 36827
60194 50133
95958 37663
68574 48860
60804 40463
99285 30498
86514 35268
78568 36730
89913 36994
66635 41831
87563 41434
89624 40740
89642 30658
78771 38490
84061 35472
67029 45196
72874 38697
91088 32916
50673 46863
56910 44507
60477 44574
98348 35464
86335 34...

output:

5627.18531240150332450867
C 6516701427555 19090335746163 468006 43038408.81050796806812286377

result:

ok jury ans = 5627.185312404, participant ans = 5627.185312402

Test #21:

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

input:

100
36940 69135
2650 85030
40502 97427
94724 76410
30024 89470
88244 38884
31880 58708
84518 54289
43910 83402
84355 56828
80732 97217
30977 88024
18859 76936
55086 57274
20500 82287
22964 67111
93768 97769
29970 91772
36269 71348
70332 52328
27049 80960
6407 72600
40903 90864
53156 84794
91227 8100...

output:

21510.22275319570326246321
C 115065815490018 164052583173778 2210226524 29068.17390994102606782690

result:

ok jury ans = 21510.222753196, participant ans = 21510.222753196

Test #22:

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

input:

100
68023 74737
73738 65097
49745 43105
96797 62905
53809 26796
84698 70442
67067 6393
71539 36404
67660 34832
66833 80545
62325 62494
75928 86937
84157 27616
73589 57334
76497 11703
56575 80314
90841 53175
64247 83001
49283 16735
62540 18314
81676 5039
57097 39741
70209 73607
75279 25719
62717 3555...

output:

23322.48250869705952936783
C 138287000455670 93996374086606 1863128900 30234.80205328422016464174

result:

ok jury ans = 23322.482508697, participant ans = 23322.482508697

Test #23:

score: 0
Accepted
time: 1112ms
memory: 6532kb

input:

1100
0 4969
2 4945
4 4929
6 4916
8 4905
10 4895
13 4881
18 4862
28 4829
35 4810
40 4797
46 4783
50 4774
55 4763
71 4731
84 4708
90 4698
103 4677
119 4653
133 4634
150 4611
161 4597
188 4565
205 4546
216 4534
241 4508
244 4505
275 4475
292 4459
304 4448
321 4433
342 4415
373 4389
388 4377
402 4366
42...

output:

4999.49356122119934298098
C 99017820 1025675640 1980 513019.45818958105519413948

result:

ok jury ans = 4999.493561221, participant ans = 4999.493561221

Test #24:

score: 0
Accepted
time: 1113ms
memory: 6532kb

input:

1100
0 4971
3 4937
4 4930
8 4905
13 4881
21 4853
27 4833
31 4821
39 4800
43 4790
51 4772
57 4759
66 4741
74 4726
92 4695
98 4685
103 4677
120 4652
127 4642
157 4602
176 4579
213 4537
236 4513
247 4502
278 4472
313 4440
330 4425
337 4419
368 4393
389 4376
425 4348
449 4330
464 4319
519 4280
547 4261
...

output:

4999.49023128242697566748
C 296100000 -2927290002 5922 499308.14228427293710410595

result:

ok jury ans = 4999.490231282, participant ans = 4999.490231282

Test #25:

score: 0
Accepted
time: 1109ms
memory: 6596kb

input:

1100
0 49014
3 48003
5 47564
7 47180
11 46554
13 46268
14 46143
16 45899
19 45542
21 45325
22 45222
25 44916
28 44630
32 44276
37 43851
39 43692
42 43457
48 43018
50 42879
56 42473
59 42278
67 41783
73 41430
81 40983
87 40672
90 40517
94 40315
101 39962
107 39666
117 39201
124 38891
128 38716
131 38...

output:

4999.46259759343229234219
C -4129855290 396643626 7932 525657.90666481491643935442

result:

ok jury ans = 4999.462597593, participant ans = 4999.462597593

Test #26:

score: 0
Accepted
time: 1111ms
memory: 6672kb

input:

1100
0 49100
1 48615
2 48269
4 47785
5 47555
7 47179
8 47007
9 46847
11 46538
17 45769
20 45423
21 45322
25 44928
26 44831
32 44266
34 44097
38 43767
47 43088
52 42742
54 42608
64 41967
69 41663
74 41376
80 41042
88 40609
99 40054
105 39763
110 39524
117 39207
124 38891
131 38587
133 38503
142 38129...

output:

4999.44991159538039937615
C 4163167974 394800000 7896 522251.64158946782117709517

result:

ok jury ans = 4999.449911595, participant ans = 4999.449911595

Test #27:

score: 0
Accepted
time: 3684ms
memory: 6892kb

input:

2000
0 49693
2 49452
3 49370
4 49295
6 49165
7 49111
9 49008
10 48958
18 48630
23 48451
29 48268
31 48212
34 48129
36 48078
42 47927
50 47745
53 47677
54 47655
60 47530
74 47263
81 47140
85 47073
101 46808
108 46701
118 46552
137 46290
140 46249
145 46182
157 46028
165 45929
170 45870
188 45659
197 ...

output:

0.33330037649284349754
C 238778603949028 238779004113732 4775620376 50000.41693481177935609594

result:

ok jury ans = 0.333300376, participant ans = 0.333300376

Test #28:

score: 0
Accepted
time: 3657ms
memory: 6700kb

input:

2000
0 49712
1 49581
2 49460
3 49377
6 49164
12 48860
17 48664
19 48586
22 48484
23 48452
35 48106
39 48003
43 47905
47 47810
56 47614
63 47471
69 47355
80 47158
84 47089
102 46793
126 46438
148 46144
161 45979
176 45797
200 45521
204 45477
217 45336
233 45170
246 45036
252 44976
267 44830
280 44706...

output:

0.32323318787894095294
C 592398306391017 592398378814181 11848083266 50000.37220299588807392865

result:

ok jury ans = 0.323233188, participant ans = 0.323233188

Test #29:

score: 0
Accepted
time: 18ms
memory: 4360kb

input:

400
35034 65376
87242 59352
480 69363
82874 59856
81938 59964
85422 59562
68886 61470
13142 67902
48528 63819
33032 65607
64648 61959
71044 61221
81808 59979
19746 67140
48814 63786
64778 61944
20552 67047
26870 66318
76686 60570
60982 62382
71954 61116
50270 63618
41846 64590
9268 68349
81886 59970...

output:

0.00000000000000000000
L 11418 98956 6869365668

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #30:

score: 0
Accepted
time: 17ms
memory: 4268kb

input:

400
768 30365
6873 42982
8313 45958
25308 81081
7563 44408
18408 66821
15138 60063
468 29745
33978 98999
648 30117
9903 49244
28053 86754
1278 31419
22248 74757
11073 51662
2643 34240
738 30303
3483 35976
978 30799
29778 90319
5403 39944
23568 77485
12948 55537
16818 63535
25773 82042
26328 83189
24...

output:

0.00000000000000000000
L -71145 34425 990675765

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #31:

score: 0
Accepted
time: 17ms
memory: 4184kb

input:

400
57291 43259
59253 44458
25683 23943
3651 10479
21795 21567
88971 62619
50343 39013
51423 39673
24873 23448
23667 22711
36717 30686
16089 18080
60873 45448
50145 38892
39255 32237
66525 48902
11085 15022
46707 36791
48705 38012
70719 51465
34593 29388
66489 48880
51585 39772
80655 57537
52971 406...

output:

0.00000000000000000000
L -60632 99216 818317032

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #32:

score: 0
Accepted
time: 5ms
memory: 4056kb

input:

200
96600 26052
60564 34515
1560 48372
37200 40002
79572 30051
11856 45954
30072 41676
24132 43071
22152 43536
93036 26889
13044 45675
4332 47721
49476 37119
24528 42978
47100 37677
52644 36375
15420 45117
42744 38700
98184 25680
51852 36561
34824 40560
32844 41025
23340 43257
53832 36096
11460 4604...

output:

0.00000000000000000000
L 23250 99000 4825098000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #33:

score: 0
Accepted
time: 5ms
memory: 4112kb

input:

200
10835 95282
69400 59038
23555 87410
55885 67402
40250 77078
19315 90034
30710 82982
55620 67566
6860 97742
42370 75766
52175 69698
14280 93150
3415 99874
41045 76586
45285 73962
18520 90526
80265 52314
81060 51822
76025 54938
99345 40506
29385 83802
60655 64450
4475 99218
82915 50674
12955 93970...

output:

0.00000000000000000000
L 59368 95930 9783654540

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #34:

score: 0
Accepted
time: 5ms
memory: 4104kb

input:

200
73206 52053
73394 52147
59576 45238
58636 44768
79504 55202
15020 22960
40212 35556
49706 40303
20190 25545
6842 18871
29120 30010
91724 61312
78188 54544
2048 16474
98868 64884
68224 49562
40400 35650
75932 53416
61644 46272
46792 38846
69446 50173
72548 51724
42562 36731
78094 54497
15866 2338...

output:

0.00000000000000000000
L -49726 99452 1536533400

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #35:

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

input:

28
53013 50869
48913 47069
51113 47069
49776 46878
48333 47359
53129 50231
46897 49757
51693 52629
50013 53119
46897 50231
51693 47359
49138 52994
48138 52494
49138 46994
47013 50869
47378 48314
51888 52494
50013 46869
52513 51869
47088 51094
52648 51674
50250 46878
52938 48894
51113 52919
48333 526...

output:

0.00000000000000000000
C 6976313370 6973663060 139490 3125.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #36:

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

input:

25
35007 54374
50007 34374
40632 37499
61760 60295
65007 45624
65587 51184
55507 35374
35382 44499
60303 38246
58407 36824
39711 61752
63182 41599
55507 64624
44507 64624
59382 62499
63182 58399
36832 41599
35382 55499
37507 59374
37507 40624
34427 48814
62507 40624
64632 44499
34427 51184
65632 49999

output:

0.00000000000000000000
C 27191306250 27186956250 543750 15625.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #37:

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

input:

90
55302 18378
62323 79561
41418 80856
61659 20133
18786 57240
81321 56745
42110 81040
62918 20656
63570 79010
81115 57637
22185 34065
18939 42093
27754 73048
20418 62306
19177 41209
18675 56745
53755 81805
50714 82018
34918 21706
28422 26288
52275 81945
46043 18181
66267 77589
25874 28888
22651 332...

output:

0.00000000000000000000
C 9944602200 9941220900 198900 32045.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #38:

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

input:

59
44569 51035
52040 44866
44991 47659
44505 49387
47116 45284
49384 55490
46496 54274
53948 53860
54553 46875
54416 46684
45576 53314
44641 51359
47191 45239
45911 53719
44863 52043
53716 54084
47116 54714
49384 44508
47871 55099
55351 48639
45439 53123
46528 54300
44912 47836
54756 47194
54711 528...

output:

0.00000000000000000000
C 2619290440 2619447610 52390 5525.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #39:

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

input:

44
48340 47355
48920 47065
52520 48115
50257 46874
47385 48310
53145 49990
51895 52490
50020 46865
51700 52625
51895 47490
52655 51670
49783 53106
46904 49753
47520 48115
52520 51865
46895 49990
48145 47490
50895 46990
48340 52625
53136 49753
49145 52990
51120 52915
52655 48310
48920 52915
47095 488...

output:

0.00000000000000000000
C 1087935000 1087282500 21750 3125.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #40:

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

input:

39
65010 45631
60306 61759
55510 64631
38257 60302
51195 34426
48825 34426
44510 64631
39714 61759
65590 51191
50010 65631
65010 54381
64635 44506
34385 50006
62510 40631
37510 59381
45635 35006
36835 58406
62510 59381
34430 51191
64635 55506
59385 62506
55510 35381
35385 44506
58410 63181
51195 655...

output:

0.00000000000000000000
C 27192937500 27190762500 543750 15625.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #41:

score: 0
Accepted
time: 35ms
memory: 4268kb

input:

280
51368 17965
47728 18017
46050 18181
67056 22849
65085 21706
20425 62306
77613 66250
31714 23669
77936 65689
38344 79829
74800 70281
17989 48618
81217 42722
75394 69533
67258 76985
19624 60173
18402 44677
79330 62901
20085 61456
58777 80802
71098 25857
49289 82018
57264 18769
55309 18378
81673 54...

output:

0.00000000000000000000
C 2218721850 2217656970 44370 32045.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #42:

score: 0
Accepted
time: 12ms
memory: 4116kb

input:

158
48683 44641
45288 47126
44595 51137
46535 45705
46688 45586
48683 55371
55494 49394
44478 50006
44870 47962
55523 49771
44648 48646
45702 53474
52343 45001
54423 46691
45128 47406
45583 46691
53471 54307
52343 55011
44503 50531
48967 44579
52047 44873
47403 45131
49478 55506
49391 44515
48456 55...

output:

0.00000000000000000000
C 8500510 8501020 170 5525.00000000000000000000

result:

ok jury ans = 0.000000000, participant ans = 0.000000000

Test #43:

score: 0
Accepted
time: 1754ms
memory: 6700kb

input:

2780
43634 9527
30398 29204
30402 29237
30411 29218
43626 9478
43706 9456
30436 29192
43649 9550
30382 29179
43709 9527
43644 9465
30385 29239
30448 29182
30419 29238
30426 29245
30377 29168
30413 29171
43639 9549
30430 29151
30379 29219
43654 9509
30368 29234
30378 29158
43698 9503
30452 29203
3043...

output:

56.57076896675607713405
C 132600736053 61960644369 4893138 16861.98391289179562591016

result:

ok jury ans = 56.570768967, participant ans = 56.570768967

Test #44:

score: 0
Accepted
time: 2062ms
memory: 6580kb

input:

3000
35274 18457
11468 6660
35219 17956
11137 6573
10999 6016
11248 5905
14689 20868
35639 18485
35245 18515
15136 21029
35759 18417
14823 20861
14863 20861
35962 17808
15097 20761
14788 20691
14913 20639
11652 6405
11102 6301
35436 18067
11362 5883
15626 20857
14655 20210
15325 20600
11152 5906
151...

output:

680.78664903549088194268
C 7167172804384 3042752715992 295439686 13757.36567788918910082430

result:

ok jury ans = 680.786649035, participant ans = 680.786649035

Test #45:

score: 0
Accepted
time: 2097ms
memory: 6696kb

input:

3000
49015 39407
48775 38034
51749 41060
25465 42992
50182 26399
23818 37501
28057 40952
48000 19119
55225 33795
23212 44126
46354 25090
46239 16846
20113 36416
45422 20320
47046 26512
20737 37247
51122 23833
51121 37396
46767 23713
52096 26148
26144 37564
23373 37475
47978 19025
20708 39100
46180 3...

output:

6776.17022075940894865198
C 50734533870774 45091240919302 1372339652 15449.83231705800426425412

result:

ok jury ans = 6776.170220759, participant ans = 6776.170220759

Test #46:

score: 0
Accepted
time: 1644ms
memory: 6628kb

input:

2703
21451 22964
31281 37761
38355 54004
21454 22989
21446 22970
38347 54017
38352 54070
21501 23057
21465 22985
38301 54091
21444 23011
38371 54039
31329 37688
31257 37761
31276 37704
31294 37721
38289 54104
21488 23004
19204 31330
19213 31380
21506 23052
38355 54060
19191 31338
21447 23053
19183 3...

output:

3154.40181275877694133669
C 25414791304676 -5642149956896 235564304 101424.93885747694002930075

result:

ok jury ans = 3154.401812759, participant ans = 3154.401812759

Test #47:

score: 0
Accepted
time: 1788ms
memory: 6428kb

input:

2799
28393 41202
39431 13585
31349 6556
12466 24297
12973 24676
28487 41308
39814 14348
13030 24327
39711 14057
28679 41157
39977 14243
31445 6502
29144 41122
12518 24438
31211 6358
12811 24697
39956 14249
40068 14345
40256 14282
39945 13956
13137 24946
30832 6525
30894 6076
13246 24925
30714 5950
3...

output:

1704.57348831828221591422
C 25433334262244 21471610499088 909916154 16401.79261059873897465877

result:

ok jury ans = 1704.573488318, participant ans = 1704.573488318

Test #48:

score: 0
Accepted
time: 1765ms
memory: 6324kb

input:

2800
55731 53447
40124 50201
40428 50643
52854 59719
57067 55144
57183 54026
39429 51201
57370 54659
40024 50146
39446 50086
57377 54664
52666 58913
40554 49812
46784 4508
56067 54286
52798 58973
57065 54442
55746 53579
39954 51325
47274 3622
48433 3844
56740 53575
46797 3168
53209 59765
40612 51268...

output:

3756.83837328616391459946
C 43417501247670 25472021481210 807456620 25646.08192503040481824428

result:

ok jury ans = 3756.838373286, participant ans = 3756.838373286

Test #49:

score: 0
Accepted
time: 1401ms
memory: 5864kb

input:

2497
41752 19228
44525 2912
31252 11042
43448 9139
16052 48892
25294 21318
40433 55158
45875 33198
14671 5656
13591 55454
16900 36294
43434 9116
44473 2873
32465 30941
34701 17016
47338 21250
36066 15180
695 13204
36065 15216
24148 48045
52176 11474
49389 29020
43473 9087
43628 13873
14622 5678
4343...

output:

15773.41062411141865595710
C 28125777914663 19145054169293 788111182 23112.20103183831815840676

result:

ok jury ans = 15773.410624111, participant ans = 15773.410624111

Test #50:

score: 0
Accepted
time: 1388ms
memory: 6144kb

input:

2500
36288 48418
10406 37910
27385 59996
8715 8497
44976 59654
45486 60162
15058 51485
6089 9925
11079 21352
45593 59945
56627 37153
42206 1655
50021 40633
14338 15068
13418 28825
33262 54391
26646 31380
44200 9953
26929 31185
14930 51422
42013 1709
18849 54764
33170 54798
50552 16735
41829 1600
542...

output:

13332.32154655023805389646
C 38019659115021 31234682051251 1108694862 20884.70724674304074142128

result:

ok jury ans = 13332.321546550, participant ans = 13332.321546550

Test #51:

score: 0
Accepted
time: 1420ms
memory: 5848kb

input:

2500
37307 45325
30558 13213
18676 59524
4464 3353
7228 944
31560 24904
32926 28522
20110 57209
17218 5785
32016 25519
60094 35007
5578 58099
45953 50831
4027 56287
47555 51218
26967 31918
16868 54274
7238 2218
34001 26346
56705 56064
33430 26032
14054 29927
22152 2878
34696 58986
46690 52327
31967 ...

output:

18906.25828221461051725782
C 26677943241836 37474162644456 1040999096 22150.42434722739926655777

result:

ok jury ans = 18906.258282215, participant ans = 18906.258282215

Test #52:

score: 0
Accepted
time: 6489ms
memory: 7796kb

input:

3000
73303 38669
61787 30119
28049 56995
98407 37479
1203 60906
26539 29928
56594 40485
54107 168
97609 34723
35444 26264
86161 84530
6875 24695
66842 31381
94567 27333
82518 87981
18733 89018
78681 9043
53685 135
4015 69633
99472 57247
18190 11422
25167 55964
94291 73201
42604 72280
96575 31813
867...

output:

24672.38252151566848624498
C 228388041439 229519407329 4603054 25734.81033107352413935587

result:

ok jury ans = 24672.382521516, participant ans = 24672.382521516

Test #53:

score: 0
Accepted
time: 6519ms
memory: 7904kb

input:

2999
33802 51428
36854 98241
99999 50305
83792 86852
29765 34346
70644 4460
76692 7720
74464 29679
30294 4046
97998 35993
37627 98445
44737 99722
33617 97240
67493 3159
17316 12160
56344 52247
36386 98111
79104 90656
14850 85560
56467 64975
78089 91364
96169 69194
28711 72799
32584 96869
1406 61777
...

output:

24299.60970707912565558217
C 151181883348 151394161512 3025968 25750.77245426115041482262

result:

ok jury ans = 24299.609707079, participant ans = 24299.609707079

Test #54:

score: 0
Accepted
time: 6509ms
memory: 8000kb

input:

2998
57800 54626
67386 52261
32212 3270
29422 37910
93120 75311
34783 2371
28029 73636
94999 28203
55169 267
92587 23801
61912 98560
14365 85074
12244 82780
37441 47562
98386 62600
25909 93814
28892 72448
57058 99499
40431 36604
32157 54062
62520 1592
93214 75150
44128 68875
99871 53587
21287 90934
...

output:

24853.82592893558467039838
C 537417482430 562390766046 10891868 26908.69940283110918244347

result:

ok jury ans = 24853.825928936, participant ans = 24853.825928936

Test #55:

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

input:

68
46990 49106
47004 49107
48904 52907
52642 51698
52932 51118
51884 52500
53004 49107
48886 47073
53125 50237
48115 47481
47369 51662
49115 46981
48306 52633
46879 49982
46986 49123
47507 51893
48324 52617
49134 47000
50009 53125
49770 53134
52915 51081
51689 52635
48909 52925
52990 49106
52625 483...

output:

19.54094558197380138154
C 868028362784 868021909920 17360728 3125.71526388646725536091

result:

ok jury ans = 19.540945582, participant ans = 19.540945582

Test #56:

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

input:

23
38248 60286
44515 64609
35385 55488
65001 45615
48825 34408
35010 45613
35005 45617
34421 48805
64989 54384
65585 51177
48816 65570
41605 63167
62515 40609
55510 64613
37505 59367
60285 61762
38236 60305
48825 65568
35001 45615
49989 65634
40635 62488
38252 39696
58405 36817

output:

15.49424400935822632164
C 80250664829074 80240309875146 1605092956 15627.73200820752390427515

result:

ok jury ans = 15.494244009, participant ans = 15.494244009

Test #57:

score: 0
Accepted
time: 937ms
memory: 5572kb

input:

1605
81204 42754
74123 71104
22988 67266
47618 81966
26813 27911
27900 73221
75200 69811
72092 73218
32746 77015
17975 50699
57880 81072
75654 69238
22988 32760
24364 30789
20667 62933
61493 79931
60191 80392
31727 23699
81824 53773
67051 77148
17955 50729
20970 63583
68290 76323
45117 81679
71000 7...

output:

18.19039115160012443084
C 115335686339734 115324905199366 2306527972 32045.00000040164741221815

result:

ok jury ans = 18.190391152, participant ans = 18.190391152

Test #58:

score: 0
Accepted
time: 59ms
memory: 4292kb

input:

357
50527 44498
51558 55292
54269 46511
52046 55131
52157 44906
51126 44574
53954 46137
45591 53303
50623 44497
44587 51113
44503 50602
55349 48630
54754 52795
47950 44857
48634 55366
51354 55345
46042 53851
54877 47398
48691 55353
45280 47102
55095 52107
48464 55292
46511 54263
46526 54291
50519 55...

output:

15.07924088995696365600
C 2984381949894 2984262713604 59689266 5525.00525563464361766819

result:

ok jury ans = 15.079240890, participant ans = 15.079240890

Test #59:

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

input:

41
53119 50227
49765 53098
48131 47480
46878 50017
53126 50017
49137 47013
50249 53129
49779 46891
47503 51892
46887 50254
52941 48907
52503 48115
52637 48302
48332 52648
52503 51892
53131 49980
46896 50250
53127 49982
49128 52990
53118 50219
51680 52643
53003 50865
50881 52980
48141 52507
46885 502...

output:

16.09548363909811996564
C 775098157820 775028343640 15500790 3123.21596569554367306409

result:

ok jury ans = 16.095483639, participant ans = 16.095483639

Test #60:

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

input:

88
55496 64617
40610 37493
59381 37504
37496 40617
35360 44493
59370 37505
48800 65573
36810 58393
51188 34401
48799 65578
36819 58412
50006 34379
34994 45637
45609 64998
44494 64637
65574 48827
65565 51178
65609 49998
40610 62493
61749 60303
63160 58393
35006 54379
63178 58381
34996 45617
60280 617...

output:

16.09190386745740397600
C 5010270590100 5009996789600 100206140 15625.02179322070878697559

result:

ok jury ans = 16.091903867, participant ans = 16.091903867

Test #61:

score: 0
Accepted
time: 725ms
memory: 5104kb

input:

1404
81964 47735
32949 77144
82007 51346
30448 24609
77139 32948
80821 41240
30764 24360
53955 81812
65080 78273
67256 23010
72244 26931
22177 65911
65916 77825
75200 69807
52391 18041
39811 80395
37070 20670
78278 65094
77132 32947
74785 29695
38339 20150
75200 69793
31712 76326
37080 20673
30224 7...

output:

17.57449961194834031630
C 423919984562428 423870043871896 8478004824 32045.00000096960866358131

result:

ok jury ans = 17.574499612, participant ans = 17.574499612

Test #62:

score: 0
Accepted
time: 78ms
memory: 4436kb

input:

441
51021 44577
55395 48885
55540 49745
46124 53956
53939 53877
52790 54764
52792 54776
53129 54548
46513 54291
53730 54089
54745 47199
51116 55412
54562 46867
54733 52881
53874 46064
52157 44931
46889 54573
49408 44489
46126 53968
53485 54279
51370 55359
53520 54255
54575 53125
46679 45595
52890 45...

output:

24.40562820570175972534
C 2937725861720 2937395527860 58748840 5525.06626166213845863240

result:

ok jury ans = 24.405628206, participant ans = 24.405628206

Test #63:

score: 0
Accepted
time: 116ms
memory: 4468kb

input:

379
56619 21936
4278 1797
47495 21656
59215 2714
65257 9809
59962 20948
20013 20448
6638 580
62473 4831
65009 15093
774 6139
51 11015
52347 1850
63354 5809
48616 1686
23198 20588
64595 7842
59711 21069
790 6101
55987 2010
3803 17847
65429 10813
9436 14
973 14303
65181 9494
6309 19293
24472 20644
654...

output:

9999.98137354538630461320
L -2004 45591 435789339

result:

ok jury ans = 9999.981373545, participant ans = 9999.981373545

Test #64:

score: 0
Accepted
time: 85ms
memory: 4380kb

input:

400
502 1867
782 1976
757 1970
2121 2244
876 7
5828 945
745 1967
9239 3173
9377 2980
13 834
3683 516
9495 2402
1598 99
4461 2712
7671 3354
9490 2359
8061 3432
123 1482
6816 3183
7551 3330
289 295
9479 2296
8016 3423
319 1733
2093 198
585 89
3338 447
390 206
3938 567
8678 1515
5751 2970
8912 3411
114...

output:

1000.38840533987672642979
L -1503 7515 6008994

result:

ok jury ans = 1000.388405340, participant ans = 1000.388405340

Test #65:

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

input:

320
5261 14992
67720 6648
23 9511
67378 7413
3334 14713
9 9685
1124 13158
65775 839
42863 11753
1337 6594
67688 6737
3095 14622
66015 1010
67821 6323
66269 1215
64660 282
67570 7027
14849 14168
2206 5851
612 12397
63725 51
3024 5405
4000 14898
3064 5388
38165 12158
63171 1
67576 2984
1698 13754
3765...

output:

5000.17879279033058992354
L 5005 58058 605507903

result:

ok jury ans = 5000.178792790, participant ans = 5000.178792790

Test #66:

score: 0
Accepted
time: 710ms
memory: 7028kb

input:

2028
7637 2508
20456 6990
9329 3072
24521 8136
29381 9756
13253 4380
25061 8316
35180 11898
4757 1548
29345 9744
7241 2376
19124 6546
2996 1170
15308 5274
5372 1962
20129 6672
34928 11814
7061 2316
8825 2904
11744 4086
28985 9624
34820 11778
26645 8844
13541 4476
7928 2814
35576 12030
29273 9720
634...

output:

99.13740464627868220759
L 11988 -35964 -2403594

result:

ok jury ans = 99.137404646, participant ans = 99.137404646

Test #67:

score: 0
Accepted
time: 668ms
memory: 6908kb

input:

1998
1348 31328
2450 31791
39508 5888
35762 9583
18292 20032
37876 6976
6388 27968
31204 11424
48889 807
25588 15168
26500 14560
4706 30287
4708 29088
45604 1824
15794 22895
37346 8527
18484 19904
7252 27392
28466 14447
19972 18912
29330 13871
43636 3136
37828 7008
42004 4224
38404 6624
38546 7727
9...

output:

498.25945125931207257963
L 32032 48048 1577199624

result:

ok jury ans = 498.259451259, participant ans = 498.259451259