QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#34443#2875. Grand CenterYaoBIGAC ✓203ms5036kbC++176.9kb2022-06-09 08:59:522022-06-09 08:59:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-09 08:59:54]
  • 评测
  • 测评结果:AC
  • 用时:203ms
  • 内存:5036kb
  • [2022-06-09 08:59:52]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for(auto i = a; i <= (n); i++)
#define per(i, a, n) for(auto i = n; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if(b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<size_t N> string to_string(bitset<N> v) 
{
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template<class A> string to_string(A v)
{
    bool first = 1;
    string res = "{";
    for(const auto &x: v) 
    {
        if (!first) res += ", ";
        first = 0;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.FI) + ", " + to_string(p.SE) + ")"; }

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) 
{
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifndef ONLINE_JUDGE
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) if(0) puts("No effect.")
#endif

using ll = long long;
// using LL = __int128;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using db = double;
using ldb = long double;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

template<class T> struct TPoint {
    // use T = double or T = long long.   
    using P = TPoint;
    static constexpr T eps = static_cast<T>(1e-9);
    static int sgn(T x) { return (x > eps) - (x < -eps); }
    static int cmp(T x, T y) { return sgn(x - y); }
    static T sqr(T x) { return x * x; }

    T x, y;

    inline P operator +(P a) const { return P{x + a.x, y + a.y}; }
    inline P operator -(P a) const { return P{x - a.x, y - a.y}; }
    inline P operator *(T a) const { return P{x * a, y * a}; }
    inline P operator /(T a) const { return P{x / a, y / a}; }
    inline bool operator ==(P a) const { return cmp(x, a.x) == 0 && cmp(y, a.y) == 0; }
    inline bool operator <(P a) const { return cmp(x, a.x) == 0 ? cmp(y, a.y) < 0: x < a.x; }

    inline T len() const { return sqrt(sqr(x) + sqr(y)); } // I believe that you should not use this function when T = long long.
    inline T dis_to(P a) const { return (*this - a).len(); }
    inline T len2() const { return sqr(x) + sqr(y); }
    inline P unit() const {
        if (eps != 0) return len() <= eps ? P{} : *this / len(); // for float.
        else return * this; // for long long
    }

    inline T dot(P b) const { return x * b.x + y * b.y; }
    inline T cross(P b) const { return x * b.y - y * b.x; }
    inline bool is_upper() const { return y > eps || (sgn(y) == 0 && x < -eps); }
    static int cmp_polar(const P &a, const P &b) {
        if(a.is_upper() != b.is_upper()) return a.is_upper() < b.is_upper();
        return a.unit().cross(b.unit()) > eps;
        // one issue of this function is that if you use float-type and the values have large range then colinear points might be viewed as non-colinear.
    }
    P rot90() { return P{-y, x}; }

    P rotate(db theta) const {
        P a{cos(theta), sin(theta)};
        return P{x * a.x - y * a.y, x * a.y + y * a.x};
    }
    T project_len(P a, P b) const { return (*this - a).dot((b - a).unit()); } // signed.
    T dis_to_line(P a, P b) const { return (*this - a).cross((b - a).unit()); } // signed, return 0 if a == b.
    T dis_to_seg(P a, P b) const {
        if(project_len(a, b) < -eps) return (*this - a).len();
        if(project_len(b, a) < -eps) return (*this - b).len();
        return fabs(dis_to_line(a, b));
    }
    P project_to_line(P a, P b) const { return a + (b - a) * project_len(a, b); }
    bool on_seg(P a, P b) const { return dis_to_seg(a, b) <= eps; } // including vertice a and b.
    bool on_line(P a, P b) const { return sgn(dis_to_line(a, b)) == 0; }
};
using T = db;
using P = TPoint<T>;
using vp = vector<P>;

string to_string(const P& p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }

struct L
{
    P v[2];
    P& operator[](int i) const { return (P&)v[i]; }
    P dir() const { return v[1] - v[0]; }
    bool include(P p) const { return p.dis_to_line(v[0], v[1]) < -P::eps; }
    bool operator <(const L &rhs) const { return P::cmp_polar(dir(), rhs.dir()); }
    pair<int, P> intersect(const L &rhs) const
    {
        auto s0 = (v[0] - rhs[0]).cross(rhs.dir());
        auto s1 = (v[1] - rhs[0]).cross(rhs.dir());
        if(P::cmp(s0, s1) == 0) return mp(0, P{});
        return mp(1, (v[1] * s0 - v[0] * s1) / (s0 - s1));
    }
};

vp HPI(vector<L> ls)
{   // please make sure l is closed.   
    auto Samedir = [](L r, L s) { return (r < s || s < r) == 0; };
    sort(all(ls), [&](L r, L s) { return Samedir(r, s) ? s.include(r[0]) : r < s; });

    // assuming l is closed then the intersect function should be fine.
    auto check = [](L w, L r, L s) { return w.include(r.intersect(s).SE); };
    
    deque<L> q;
    rep(i, 0, sz(ls) - 1)
    {
        if(i && Samedir(ls[i], ls[i - 1])) continue;
        while(sz(q) > 1 && !check(ls[i], q[sz(q) - 2], q[sz(q) - 1])) q.pop_back();
        while(sz(q) > 1 && !check(ls[i], q[0], q[1])) q.pop_front();
        q.pb(ls[i]);
    }
	while (sz(q) > 2 && !check(q[0], q[sz(q) - 2], q[sz(q) - 1])) q.pop_back();
	while (sz(q) > 2 && !check(q[sz(q) - 1], q[0], q[1])) q.pop_front();
    vp res;
    rep(i, 0, sz(q) - 1) res.pb(q[i].intersect(q[(i + 1) % sz(q)]).SE);
    return res;
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    vp a(n);
    for(auto &[x, y]: a) cin >> x >> y;
    auto check = [&](T ratio) 
    {
        auto next = [&](int i) { return i == n - 1 ? 0 : i + 1; };
        int ptr = 1;
        vector<L> ls;
        rep(i, 0, n - 1)
        {
            P &p = a[i], &q = a[next(i)];
            while((q - p).cross(a[ptr] - p) < (q - p).cross(a[next(ptr)] - p)) ptr = next(ptr);
            P A = (p - a[ptr]) * (ratio / (1 + ratio)) + a[ptr];
            P B = (q - a[ptr]) * (ratio / (1 + ratio)) + a[ptr];
            //debug(ratio,ptr,A.x,A.y,B.x,B.y);
            ls.pb(L{A, B});
        }
        auto res = HPI(ls);
        return sz(res) >= 3;
    };
    db l = 1, r = 2;
    rep(_, 1, 60)
    {
        db mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%.10f\n", l);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0
1 0
1 1
0 1

output:

1.0000000020

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

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

input:

3
0 0
1 0
0 1

output:

2.0000000000

result:

ok found '2.0000000', expected '2.0000001', error '0.0000001'

Test #3:

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

input:

4
0 0
2 0
4 4
0 2

output:

1.5000000009

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #4:

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

input:

8
0 0
6 11
7 13
4 14
0 15
-4 14
-7 13
-6 11

output:

1.7222222224

result:

ok found '1.7222222', expected '1.7222223', error '0.0000000'

Test #5:

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

input:

4
4 -9
10 5
-8 -6
3 -10

output:

1.9569892476

result:

ok found '1.9569892', expected '1.9569892', error '0.0000000'

Test #6:

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

input:

5
-54541 -89247
-54559 -89250
-54551 -89275
-54533 -89272
-54536 -89253

output:

1.1397459166

result:

ok found '1.1397459', expected '1.1397460', error '0.0000000'

Test #7:

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

input:

6
63 64
-91 -3
-25 -74
27 -67
99 -38
84 54

output:

1.2917918461

result:

ok found '1.2917918', expected '1.2917919', error '0.0000000'

Test #8:

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

input:

11
80149 -14019
79767 -3293
70677 620
67779 733
62316 936
60731 -2509
60190 -5365
60638 -16930
64799 -18374
71197 -18839
74837 -18754

output:

1.1457063848

result:

ok found '1.1457064', expected '1.1457064', error '0.0000000'

Test #9:

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

input:

12
980 -106
993 444
995 587
774 905
326 926
-788 958
-840 942
-941 430
-948 180
-950 -894
-399 -999
914 -940

output:

1.0763530029

result:

ok found '1.0763530', expected '1.0763530', error '0.0000000'

Test #10:

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

input:

15
-9933 -2261
-9884 -7027
-9798 -9982
7786 -9980
9194 -9550
9669 -7656
9814 -6982
9996 -5356
9962 7650
9933 9862
5788 9995
-7631 9953
-8970 9941
-9948 9520
-9984 7224

output:

1.0370249514

result:

ok found '1.0370250', expected '1.0370250', error '0.0000000'

Test #11:

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

input:

26
-99388 98460
-99605 95356
-99812 89330
-100000 25496
-99984 -45172
-99821 -97539
-99764 -99159
-87881 -99941
-66037 -99971
31755 -99892
91560 -99416
97988 -98836
98477 -98775
99314 -96727
99752 -92437
99780 -91600
99903 -72727
99967 -18033
99972 61721
99882 98505
96588 99737
95044 99826
91003 999...

output:

1.0054905088

result:

ok found '1.0054905', expected '1.0054905', error '0.0000000'

Test #12:

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

input:

4
-90193 76019
41466 -97592
-18792 61801
-64035 74971

output:

1.9537091703

result:

ok found '1.9537092', expected '1.9537092', error '0.0000000'

Test #13:

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

input:

8
99217 79790
39638 88078
-39196 59201
-91442 -51225
-82115 -69068
-60816 -93795
-292 -97330
61561 -98197

output:

1.2285461774

result:

ok found '1.2285462', expected '1.2285462', error '0.0000000'

Test #14:

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

input:

15
93718 98921
-4750 99674
-91678 96071
-95667 89757
-96751 75343
-97964 45418
-97870 -15113
-96683 -84304
-64860 -97781
-59992 -97996
-20315 -99410
73859 -94388
87556 -81689
98491 -39952
98317 81106

output:

1.0625026880

result:

ok found '1.0625027', expected '1.0625027', error '0.0000000'

Test #15:

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

input:

17
-98943 93153
-99203 74457
-99786 19261
-99575 -58504
-99021 -76417
-96128 -98912
-73903 -99976
90656 -99842
98793 -95624
99268 -91899
99786 -66679
99826 36342
99723 99328
87458 99727
56646 99866
-54215 99606
-92960 99133

output:

1.0167659906

result:

ok found '1.0167660', expected '1.0167660', error '0.0000000'

Test #16:

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

input:

22
-74104 -99983
75292 -99939
95742 -98841
99573 -89793
99668 -67759
99865 28608
99814 55714
99323 95372
99149 98220
95153 99852
54240 99978
-61655 99969
-87344 99447
-97209 98230
-99840 86621
-99966 62349
-99972 25512
-99973 -12748
-99949 -35127
-99472 -87562
-99387 -88291
-97150 -98379

output:

1.0103928769

result:

ok found '1.0103929', expected '1.0103929', error '0.0000000'

Test #17:

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

input:

26
-99383 98459
-99600 95355
-99807 89329
-99995 25495
-99979 -45173
-99816 -97540
-99759 -99160
-87876 -99942
-66032 -99972
31760 -99893
91565 -99417
97993 -98837
98482 -98776
99319 -96728
99757 -92438
99785 -91601
99908 -72728
99972 -18034
99977 61720
99887 98504
96593 99736
95049 99825
91008 9992...

output:

1.0054905088

result:

ok found '1.0054905', expected '1.0054905', error '0.0000000'

Test #18:

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

input:

4
8 5
0 9
0 -9
2 -9

output:

1.7941176474

result:

ok found '1.7941176', expected '1.7941177', error '0.0000000'

Test #19:

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

input:

4
91928 71582
91925 71587
91924 71559
91930 71571

output:

1.7444444449

result:

ok found '1.7444444', expected '1.7444445', error '0.0000000'

Test #20:

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

input:

10
58 80
38 92
-38 92
-73 67
-87 48
-91 41
-92 -38
-88 -47
-57 -81
47 -87

output:

1.2106130099

result:

ok found '1.2106130', expected '1.2106130', error '0.0000000'

Test #21:

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

input:

50
29321 58885
28559 58425
26500 56598
26425 56509
24132 50853
24403 47676
24455 47476
24828 46367
25280 45398
25384 45208
27104 42961
27944 42226
28139 42077
28565 41777
29632 41159
31272 40513
32028 40321
32045 40318
33583 40117
33750 40110
34771 40126
35703 40232
37442 40677
37546 40715
38316 410...

output:

1.0259999251

result:

ok found '1.0259999', expected '1.0259999', error '0.0000000'

Test #22:

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

input:

83
319 947
154 988
125 992
11 999
0 999
-173 984
-248 968
-417 908
-558 829
-680 732
-695 718
-721 692
-849 527
-856 516
-875 483
-910 413
-916 399
-936 349
-946 322
-969 243
-981 189
-993 117
-978 -208
-966 -256
-940 -339
-927 -374
-913 -406
-900 -435
-882 -470
-845 -534
-812 -583
-757 -653
-670 -7...

output:

1.0091652907

result:

ok found '1.0091653', expected '1.0091653', error '0.0000000'

Test #23:

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

input:

553
2928 9561
2853 9584
2810 9597
2682 9633
2628 9648
2505 9681
2390 9710
2335 9723
2134 9769
2075 9782
1958 9806
1705 9853
1642 9864
1618 9868
1434 9896
1361 9906
1037 9946
915 9958
764 9970
738 9972
625 9980
542 9985
413 9991
390 9992
279 9996
189 9998
61 9999
-62 9999
-181 9998
-295 9995
-404 999...

output:

1.0002375699

result:

ok found '1.0002376', expected '1.0002376', error '0.0000000'

Test #24:

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

input:

4
55420 68568
-90657 3904
-65122 -88325
91518 -71805

output:

1.3416424012

result:

ok found '1.3416424', expected '1.3416424', error '0.0000000'

Test #25:

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

input:

20
64629 78992
52700 86846
35604 94422
33359 95146
-1942 99445
-12396 98288
-12667 98243
-17690 97271
-91679 29294
-93798 21338
-96186 -240
-92881 -25886
-84662 -46994
-80210 -54610
-78926 -56550
-9435 -99507
20256 -99027
78588 -66786
97159 -36256
89935 50433

output:

1.1161795902

result:

ok found '1.1161796', expected '1.1161796', error '0.0000000'

Test #26:

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

input:

296
-30745 -95160
-24796 -96879
-24008 -97078
-23716 -97149
-21384 -97689
-19555 -98071
-17574 -98445
-14584 -98932
-14477 -98948
-12957 -99158
-11624 -99323
-11255 -99365
-10640 -99433
-9845 -99515
-990 -99995
3139 -99950
5851 -99827
6806 -99767
7252 -99735
8874 -99604
10775 -99416
12374 -99229
131...

output:

1.0016459822

result:

ok found '1.0016460', expected '1.0016460', error '0.0000000'

Test #27:

score: 0
Accepted
time: 23ms
memory: 4008kb

input:

1379
10703 -99425
10874 -99406
11541 -99331
11584 -99326
11644 -99319
11845 -99295
12487 -99217
13064 -99142
13390 -99099
13904 -99028
14381 -98960
15049 -98860
17038 -98537
17184 -98512
17298 -98492
17969 -98372
18257 -98319
18500 -98273
19164 -98146
19317 -98116
19393 -98101
19922 -97995
20286 -97...

output:

1.0000550294

result:

ok found '1.0000550', expected '1.0000550', error '0.0000000'

Test #28:

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

input:

2083
-33234 -94315
-33070 -94373
-32613 -94532
-32222 -94666
-32104 -94706
-31857 -94789
-31575 -94883
-31262 -94987
-31049 -95057
-30735 -95159
-30474 -95243
-30263 -95310
-30074 -95370
-29825 -95448
-29439 -95568
-29027 -95694
-28653 -95806
-28388 -95885
-28256 -95924
-28056 -95983
-27608 -96113
-...

output:

1.0000160514

result:

ok found '1.0000161', expected '1.0000161', error '0.0000000'

Test #29:

score: 0
Accepted
time: 66ms
memory: 4068kb

input:

2533
-98810 15387
-98849 15133
-98907 14748
-98947 14479
-99004 14085
-99034 13872
-99057 13706
-99093 13443
-99119 13251
-99131 13161
-99185 12747
-99216 12501
-99238 12326
-99251 12221
-99263 12123
-99292 11883
-99317 11675
-99335 11521
-99363 11275
-99403 10918
-99435 10622
-99452 10463
-99478 10...

output:

1.0000083638

result:

ok found '1.0000084', expected '1.0000084', error '0.0000000'

Test #30:

score: 0
Accepted
time: 162ms
memory: 4900kb

input:

10000
2725 -68897
2726 -68897
2798 -68896
2869 -68895
2939 -68894
3008 -68893
3076 -68892
3143 -68891
3209 -68890
3274 -68889
3338 -68888
3401 -68887
3463 -68886
3524 -68885
3584 -68884
3643 -68883
3701 -68882
3758 -68881
3814 -68880
3869 -68879
3923 -68878
3976 -68877
4028 -68876
4079 -68875
4129 -...

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #31:

score: 0
Accepted
time: 170ms
memory: 4812kb

input:

9999
-7403 -78743
-7328 -78742
-7255 -78741
-7183 -78740
-7112 -78739
-7042 -78738
-6973 -78737
-6905 -78736
-6838 -78735
-6772 -78734
-6707 -78733
-6643 -78732
-6580 -78731
-6518 -78730
-6457 -78729
-6397 -78728
-6338 -78727
-6280 -78726
-6223 -78725
-6167 -78724
-6112 -78723
-6058 -78722
-6005 -78...

output:

1.0000007713

result:

ok found '1.0000008', expected '1.0000008', error '0.0000000'

Test #32:

score: 0
Accepted
time: 171ms
memory: 4804kb

input:

9998
8840 -85736
8841 -85736
8916 -85735
8990 -85734
9063 -85733
9206 -85731
9276 -85730
9345 -85729
9413 -85728
9480 -85727
9546 -85726
9611 -85725
9675 -85724
9738 -85723
9800 -85722
9921 -85720
9980 -85719
10038 -85718
10151 -85716
10206 -85715
10260 -85714
10313 -85713
10365 -85712
10466 -85710
...

output:

1.0000008548

result:

ok found '1.0000009', expected '1.0000009', error '0.0000000'

Test #33:

score: 0
Accepted
time: 169ms
memory: 4816kb

input:

9997
-1454 -90851
-1377 -90850
-1301 -90849
-1226 -90848
-1152 -90847
-1079 -90846
-1007 -90845
-936 -90844
-866 -90843
-729 -90841
-662 -90840
-531 -90838
-404 -90836
-342 -90835
-281 -90834
-221 -90833
-162 -90832
-104 -90831
-47 -90830
9 -90829
64 -90828
118 -90827
171 -90826
223 -90825
274 -9082...

output:

1.0000013116

result:

ok found '1.0000013', expected '1.0000013', error '0.0000000'

Test #34:

score: 0
Accepted
time: 154ms
memory: 4812kb

input:

9996
4600 -90225
4601 -90225
4675 -90224
4748 -90223
4820 -90222
4891 -90221
4961 -90220
5030 -90219
5098 -90218
5165 -90217
5231 -90216
5296 -90215
5360 -90214
5423 -90213
5485 -90212
5546 -90211
5665 -90209
5723 -90208
5780 -90207
5836 -90206
5945 -90204
5998 -90203
6050 -90202
6101 -90201
6151 -9...

output:

1.0000008798

result:

ok found '1.0000009', expected '1.0000009', error '0.0000000'

Test #35:

score: 0
Accepted
time: 179ms
memory: 4840kb

input:

9995
-298 -86555
-297 -86555
-222 -86554
-148 -86553
-75 -86552
-3 -86551
68 -86550
138 -86549
207 -86548
275 -86547
342 -86546
408 -86545
473 -86544
537 -86543
600 -86542
662 -86541
783 -86539
842 -86538
900 -86537
957 -86536
1068 -86534
1122 -86533
1175 -86532
1227 -86531
1278 -86530
1328 -86529
1...

output:

1.0000010963

result:

ok found '1.0000011', expected '1.0000011', error '0.0000000'

Test #36:

score: 0
Accepted
time: 171ms
memory: 4876kb

input:

9994
3455 -94088
3456 -94088
3533 -94087
3609 -94086
3684 -94085
3831 -94083
3903 -94082
3974 -94081
4044 -94080
4113 -94079
4181 -94078
4248 -94077
4314 -94076
4379 -94075
4443 -94074
4506 -94073
4568 -94072
4629 -94071
4689 -94070
4748 -94069
4806 -94068
4863 -94067
4974 -94065
5081 -94063
5133 -9...

output:

1.0000022199

result:

ok found '1.0000022', expected '1.0000022', error '0.0000000'

Test #37:

score: 0
Accepted
time: 184ms
memory: 4932kb

input:

9999
15338 -89944
15339 -89944
15413 -89943
15486 -89942
15558 -89941
15629 -89940
15699 -89939
15768 -89938
15836 -89937
15903 -89936
15969 -89935
16034 -89934
16098 -89933
16161 -89932
16223 -89931
16284 -89930
16344 -89929
16403 -89928
16461 -89927
16518 -89926
16574 -89925
16629 -89924
16683 -89...

output:

1.0056086587

result:

ok found '1.0056087', expected '1.0056087', error '0.0000000'

Test #38:

score: 0
Accepted
time: 181ms
memory: 4896kb

input:

9998
5960 -79984
5961 -79984
6036 -79983
6110 -79982
6183 -79981
6255 -79980
6326 -79979
6396 -79978
6465 -79977
6533 -79976
6600 -79975
6666 -79974
6731 -79973
6795 -79972
6858 -79971
6920 -79970
6981 -79969
7041 -79968
7100 -79967
7158 -79966
7215 -79965
7271 -79964
7326 -79963
7380 -79962
7433 -7...

output:

1.0204112569

result:

ok found '1.0204113', expected '1.0204113', error '0.0000000'

Test #39:

score: 0
Accepted
time: 202ms
memory: 4836kb

input:

9997
-83 -89362
-82 -89362
-5 -89361
71 -89360
146 -89359
220 -89358
293 -89357
365 -89356
436 -89355
506 -89354
575 -89353
643 -89352
710 -89351
776 -89350
841 -89349
905 -89348
968 -89347
1030 -89346
1091 -89345
1151 -89344
1210 -89343
1268 -89342
1325 -89341
1381 -89340
1436 -89339
1490 -89338
15...

output:

1.0416330729

result:

ok found '1.0416331', expected '1.0416331', error '0.0000000'

Test #40:

score: 0
Accepted
time: 171ms
memory: 4880kb

input:

9996
5936 -71657
5937 -71657
6011 -71656
6084 -71655
6156 -71654
6227 -71653
6297 -71652
6366 -71651
6434 -71650
6501 -71649
6567 -71648
6632 -71647
6696 -71646
6759 -71645
6821 -71644
6882 -71643
6942 -71642
7001 -71641
7059 -71640
7116 -71639
7172 -71638
7227 -71637
7281 -71636
7334 -71635
7386 -7...

output:

1.0057261516

result:

ok found '1.0057262', expected '1.0057262', error '0.0000000'

Test #41:

score: 0
Accepted
time: 179ms
memory: 4808kb

input:

9995
9675 -80779
9676 -80779
9751 -80778
9825 -80777
9898 -80776
9970 -80775
10041 -80774
10111 -80773
10180 -80772
10248 -80771
10315 -80770
10381 -80769
10446 -80768
10510 -80767
10573 -80766
10635 -80765
10696 -80764
10756 -80763
10815 -80762
10873 -80761
10930 -80760
10986 -80759
11041 -80758
11...

output:

1.0206087356

result:

ok found '1.0206087', expected '1.0206087', error '0.0000000'

Test #42:

score: 0
Accepted
time: 203ms
memory: 5036kb

input:

9994
4060 -92187
4061 -92187
4138 -92186
4214 -92185
4289 -92184
4363 -92183
4436 -92182
4508 -92181
4579 -92180
4649 -92179
4718 -92178
4786 -92177
4853 -92176
4919 -92175
4984 -92174
5048 -92173
5111 -92172
5173 -92171
5234 -92170
5294 -92169
5353 -92168
5411 -92167
5468 -92166
5524 -92165
5579 -9...

output:

1.0416277362

result:

ok found '1.0416277', expected '1.0416278', error '0.0000000'

Test #43:

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

input:

4
7 3
3 2
3 -7
5 -8

output:

1.5000000007

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #44:

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

input:

4
96779 -5192
96777 -5192
96773 -5195
96783 -5201

output:

1.8888888893

result:

ok found '1.8888889', expected '1.8888889', error '0.0000000'

Test #45:

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

input:

24
-99859 -97470
-96124 -99283
-89730 -99640
-76970 -99864
-14506 -99913
51062 -99894
84680 -99867
95930 -98282
99301 -93606
99770 -87046
99910 -54286
99908 -17214
99847 30188
99725 91356
98811 95728
98481 96525
96123 98984
88186 99806
82187 99938
-95431 99840
-97882 99783
-99439 98679
-99906 79987
...

output:

1.0115146963

result:

ok found '1.0115147', expected '1.0115147', error '0.0000000'

Test #46:

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

input:

19
-98173 -99824
-59365 -99908
-46360 -99917
88239 -99969
99565 -99902
99591 -99032
99876 -88755
99947 -32689
99955 43797
99896 76984
99827 99526
96550 99846
-8094 99979
-94848 99877
-96975 99263
-99662 91264
-99993 44387
-99979 -97124
-99176 -99102

output:

1.0112098313

result:

ok found '1.0112098', expected '1.0112098', error '0.0000000'

Test #47:

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

input:

5
10 -7
10 7
2 12
-6 11
-9 -8

output:

1.2796803951

result:

ok found '1.2796804', expected '1.2796804', error '0.0000000'

Test #48:

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

input:

6
-52809 -67247
-52812 -67243
-52820 -67241
-52833 -67251
-52833 -67252
-52820 -67267

output:

1.4375217544

result:

ok found '1.4375218', expected '1.4375218', error '0.0000000'

Test #49:

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

input:

2559
-69326 -72067
-69024 -72356
-68851 -72521
-68768 -72600
-68463 -72887
-68290 -73049
-68093 -73233
-67782 -73521
-67551 -73733
-67339 -73927
-67168 -74082
-66947 -74282
-66897 -74327
-66779 -74433
-66671 -74530
-66309 -74852
-66084 -75051
-65945 -75173
-65589 -75484
-65417 -75633
-65199 -75821
-...

output:

1.0000083005

result:

ok found '1.0000083', expected '1.0000083', error '0.0000000'

Test #50:

score: 0
Accepted
time: 50ms
memory: 4084kb

input:

2521
-84671 -53205
-84614 -53296
-84415 -53610
-84305 -53783
-84198 -53950
-84171 -53992
-83995 -54265
-83802 -54563
-83746 -54649
-83585 -54895
-83435 -55123
-83304 -55321
-83144 -55561
-83003 -55771
-82894 -55933
-82773 -56112
-82610 -56352
-82488 -56530
-82411 -56642
-82228 -56908
-81975 -57271
-...

output:

1.0000072792

result:

ok found '1.0000073', expected '1.0000073', error '0.0000000'

Test #51:

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

input:

1609
16500 93612
16309 93487
16086 93337
15918 93223
15798 93140
15745 93103
15574 92983
15388 92850
15370 92837
15233 92738
15102 92642
15079 92625
14913 92502
14763 92389
14726 92361
14648 92301
14376 92091
14255 91996
14064 91845
13964 91765
13811 91641
13660 91518
13521 91403
13372 91279
13316 9...

output:

1.0000264254

result:

ok found '1.0000264', expected '1.0000264', error '0.0000000'

Test #52:

score: 0
Accepted
time: 46ms
memory: 3924kb

input:

1676
-75496 32111
-75414 32024
-75239 31839
-75203 31801
-74986 31572
-74630 31200
-74554 31121
-74445 31008
-74302 30860
-74207 30762
-74106 30658
-73970 30518
-73619 30160
-73378 29915
-73276 29812
-73129 29664
-72899 29433
-72712 29246
-72409 28945
-72173 28711
-72043 28583
-71985 28526
-71764 28...

output:

1.0000227940

result:

ok found '1.0000228', expected '1.0000228', error '0.0000000'

Test #53:

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

input:

1719
-2199 97275
-2246 97162
-2255 97140
-2279 97081
-2298 97034
-2340 96929
-2378 96832
-2448 96650
-2508 96489
-2549 96377
-2577 96299
-2597 96243
-2625 96164
-2664 96052
-2693 95968
-2703 95939
-2751 95797
-2774 95728
-2802 95643
-2819 95591
-2868 95440
-2936 95226
-2991 95048
-3040 94887
-3057 9...

output:

1.0000188683

result:

ok found '1.0000189', expected '1.0000189', error '0.0000000'

Test #54:

score: 0
Accepted
time: 22ms
memory: 4044kb

input:

1329
-4595 -10731
-4207 -10390
-3685 -9931
-2918 -9256
-2431 -8827
-2187 -8612
-1449 -7961
-938 -7510
-758 -7351
-37 -6714
1519 -5336
1589 -5274
1993 -4916
2488 -4477
2807 -4194
2914 -4099
3289 -3766
3432 -3639
3808 -3305
4574 -2624
4874 -2357
5375 -1911
5439 -1854
5989 -1364
6348 -1044
7632 101
819...

output:

1.0000443777

result:

ok found '1.0000444', expected '1.0000444', error '0.0000000'

Test #55:

score: 0
Accepted
time: 40ms
memory: 3988kb

input:

1821
91451 -50903
91515 -50811
91615 -50665
91701 -50537
91789 -50405
91890 -50252
92052 -50001
92165 -49820
92281 -49633
92319 -49571
92391 -49451
92480 -49302
92561 -49164
92619 -49065
92771 -48797
92789 -48765
92817 -48715
92856 -48644
92929 -48511
92948 -48476
92981 -48415
93030 -48323
93089 -48...

output:

1.0000169325

result:

ok found '1.0000169', expected '1.0000170', error '0.0000000'

Test #56:

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

input:

1824
47433 5196
48131 5343
48385 5397
48629 5449
49242 5581
49464 5629
49621 5663
49964 5738
50277 5807
50810 5925
50968 5960
51094 5988
51722 6129
52145 6225
52800 6375
52852 6387
53120 6449
53275 6485
53648 6572
54211 6704
54514 6776
55059 6906
55196 6939
55428 6995
55725 7067
55881 7105
56275 720...

output:

1.0000176998

result:

ok found '1.0000177', expected '1.0000177', error '0.0000000'

Test #57:

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

input:

1776
53357 12034
52763 11857
52367 11738
51946 11611
51658 11524
51569 11497
51349 11430
50998 11323
50638 11213
50225 11086
50011 11020
49710 10927
49472 10853
49308 10802
49141 10750
48705 10614
48275 10479
48116 10429
48027 10401
47580 10260
47457 10221
47095 10106
46828 10021
46612 9952
46318 98...

output:

1.0000236708

result:

ok found '1.0000237', expected '1.0000237', error '0.0000000'

Test #58:

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

input:

1146
-27741 46748
-27347 46061
-27192 45791
-26898 45279
-26759 45037
-26460 44517
-26372 44364
-26307 44251
-26109 43907
-25972 43669
-25877 43504
-25749 43282
-25350 42590
-24837 41701
-24522 41156
-24400 40945
-24230 40651
-24042 40326
-23646 39642
-23467 39333
-23296 39038
-23020 38562
-22846 38...

output:

1.0000512787

result:

ok found '1.0000513', expected '1.0000513', error '0.0000000'

Test #59:

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

input:

427
49606 -77019
50075 -77903
50429 -78570
50583 -78860
50942 -79536
51917 -81371
52102 -81719
52677 -82800
52735 -82909
53124 -83640
53411 -84179
54147 -85560
54596 -86402
54762 -86713
55101 -87348
55797 -88650
56055 -89132
56108 -89231
56296 -89582
56491 -89946
56847 -90610
56956 -90813
57287 -914...

output:

1.0003974639

result:

ok found '1.0003975', expected '1.0003975', error '0.0000000'

Test #60:

score: 0
Accepted
time: 24ms
memory: 3948kb

input:

1157
-28170 84522
-28192 84554
-28261 84653
-28314 84728
-28369 84805
-28393 84838
-28412 84864
-28446 84910
-28469 84941
-28514 85001
-28543 85039
-28574 85079
-28581 85088
-28620 85138
-28664 85193
-28686 85220
-28753 85301
-28764 85314
-28783 85336
-28803 85359
-28846 85408
-28888 85454
-28917 85...

output:

1.0000513776

result:

ok found '1.0000514', expected '1.0000514', error '0.0000000'

Test #61:

score: 0
Accepted
time: 51ms
memory: 4084kb

input:

1857
-38575 35403
-38455 35188
-38422 35129
-38371 35038
-38240 34805
-38165 34672
-38082 34525
-38000 34380
-37936 34267
-37835 34089
-37728 33901
-37667 33794
-37566 33617
-37362 33261
-37176 32938
-37015 32659
-36877 32421
-36759 32218
-36607 31957
-36551 31861
-36400 31603
-36342 31504
-36291 31...

output:

1.0000211811

result:

ok found '1.0000212', expected '1.0000212', error '0.0000000'

Test #62:

score: 0
Accepted
time: 39ms
memory: 4124kb

input:

2577
87591 66244
87706 66300
87875 66383
87998 66444
88123 66506
88336 66613
88618 66756
88665 66780
88706 66801
88898 66900
88927 66915
89054 66981
89178 67046
89273 67096
89343 67133
89460 67195
89732 67341
89920 67443
90093 67538
90151 67570
90279 67641
90399 67708
90525 67779
90633 67840
90698 6...

output:

1.0000085043

result:

ok found '1.0000085', expected '1.0000085', error '0.0000000'

Test #63:

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

input:

1000
16500 93612
16309 93487
16086 93337
15918 93223
15798 93140
15745 93103
15574 92983
15388 92850
15370 92837
15233 92738
15102 92642
15079 92625
14913 92502
14763 92389
14726 92361
14648 92301
14376 92091
14255 91996
14064 91845
13964 91765
13811 91641
13660 91518
13521 91403
13372 91279
13316 9...

output:

1.3044290755

result:

ok found '1.3044291', expected '1.3044291', error '0.0000000'

Test #64:

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

input:

999
-75496 32111
-75414 32024
-75239 31839
-75203 31801
-74986 31572
-74630 31200
-74554 31121
-74445 31008
-74302 30860
-74207 30762
-74106 30658
-73970 30518
-73619 30160
-73378 29915
-73276 29812
-73129 29664
-72899 29433
-72712 29246
-72409 28945
-72173 28711
-72043 28583
-71985 28526
-71764 283...

output:

1.2945362088

result:

ok found '1.2945362', expected '1.2945362', error '0.0000000'

Test #65:

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

input:

1001
-4778 87256
-4849 86858
-4880 86681
-4925 86422
-4956 86242
-5002 85973
-5030 85807
-5089 85454
-5095 85418
-5146 85108
-5198 84787
-5230 84588
-5296 84171
-5331 83948
-5368 83709
-5407 83454
-5432 83290
-5439 83244
-5488 82919
-5495 82872
-5517 82724
-5535 82602
-5573 82344
-5595 82194
-5648 8...

output:

1.3247170239

result:

ok found '1.3247170', expected '1.3247170', error '0.0000000'

Test #66:

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

input:

998
35880 25858
36164 26123
36711 26634
37076 26975
37495 27367
37839 27689
38059 27895
38459 28270
38732 28526
39055 28829
39367 29122
39450 29200
39799 29528
40286 29986
41010 30668
41607 31231
42094 31691
42421 32000
42737 32299
43072 32616
43510 33031
43799 33305
43935 33434
44527 33996
45098 34...

output:

1.1832915994

result:

ok found '1.1832916', expected '1.1832916', error '0.0000000'

Test #67:

score: 0
Accepted
time: 20ms
memory: 3908kb

input:

1002
77100 -79741
77164 -79649
77264 -79503
77350 -79375
77438 -79243
77539 -79090
77701 -78839
77814 -78658
77930 -78471
77968 -78409
78040 -78289
78129 -78140
78210 -78002
78268 -77903
78420 -77635
78438 -77603
78466 -77553
78505 -77482
78578 -77349
78597 -77314
78630 -77253
78679 -77161
78738 -77...

output:

1.3598893551

result:

ok found '1.3598894', expected '1.3598894', error '0.0000000'

Test #68:

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

input:

997
47428 33522
48126 33669
48380 33723
48624 33775
49237 33907
49459 33955
49616 33989
49959 34064
50272 34133
50805 34251
50963 34286
51089 34314
51717 34455
52140 34551
52795 34701
52847 34713
53115 34775
53270 34811
53643 34898
54206 35030
54509 35102
55054 35232
55191 35265
55423 35321
55720 35...

output:

1.3731600227

result:

ok found '1.3731600', expected '1.3731601', error '0.0000000'

Test #69:

score: 0
Accepted
time: 23ms
memory: 3912kb

input:

1003
45893 90040
45299 89863
44903 89744
44482 89617
44194 89530
44105 89503
43885 89436
43534 89329
43174 89219
42761 89092
42547 89026
42246 88933
42008 88859
41844 88808
41677 88756
41241 88620
40811 88485
40652 88435
40563 88407
40116 88266
39993 88227
39631 88112
39364 88027
39148 87958
38854 8...

output:

1.3370343176

result:

ok found '1.3370343', expected '1.3370344', error '0.0000000'

Test #70:

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

input:

996
-65163 65340
-64769 64653
-64614 64383
-64320 63871
-64181 63629
-63882 63109
-63794 62956
-63729 62843
-63531 62499
-63394 62261
-63299 62096
-63171 61874
-62772 61182
-62259 60293
-61944 59748
-61822 59537
-61652 59243
-61464 58918
-61068 58234
-60889 57925
-60718 57630
-60442 57154
-60268 568...

output:

1.0489790564

result:

ok found '1.0489791', expected '1.0489791', error '0.0000000'

Test #71:

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

input:

995
-20231 94077
-20253 94109
-20322 94208
-20375 94283
-20430 94360
-20454 94393
-20473 94419
-20507 94465
-20530 94496
-20575 94556
-20604 94594
-20635 94634
-20642 94643
-20681 94693
-20725 94748
-20747 94775
-20814 94856
-20825 94869
-20844 94891
-20864 94914
-20907 94963
-20949 95009
-20978 950...

output:

1.0750266363

result:

ok found '1.0750266', expected '1.0750267', error '0.0000000'

Test #72:

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

input:

1003
-83704 -2568
-83584 -2783
-83551 -2842
-83500 -2933
-83369 -3166
-83294 -3299
-83211 -3446
-83129 -3591
-83065 -3704
-82964 -3882
-82857 -4070
-82796 -4177
-82695 -4354
-82491 -4710
-82305 -5033
-82144 -5312
-82006 -5550
-81888 -5753
-81736 -6014
-81680 -6110
-81529 -6368
-81471 -6467
-81420 -6...

output:

1.3689996659

result:

ok found '1.3689997', expected '1.3689997', error '0.0000000'

Test #73:

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

input:

2000
87566 13673
87681 13729
87850 13812
87973 13873
88098 13935
88311 14042
88593 14185
88640 14209
88681 14230
88873 14329
88902 14344
89029 14410
89153 14475
89248 14525
89318 14562
89435 14624
89707 14770
89895 14872
90068 14967
90126 14999
90254 15070
90374 15137
90500 15208
90608 15269
90673 1...

output:

1.1205590514

result:

ok found '1.1205591', expected '1.1205591', error '0.0000000'

Test #74:

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

input:

4
80533 -100000
80534 -100000
80534 100000
80533 100000

output:

1.0000000020

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #75:

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

input:

4
-100000 -9812
100000 -9812
100000 -9811
-100000 -9811

output:

1.0000000020

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #76:

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

input:

4
0 0
100000 0
100000 100000
0 100000

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #77:

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

input:

4
-93872 -11568
6128 -11568
6128 88432
-93872 88432

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #78:

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

input:

4
-92431 -54274
57569 -54274
57569 95726
-92431 95726

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #79:

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

input:

4
-99999 -100000
100000 -100000
100000 99999
-99999 99999

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'