QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735217#5104. Guardians of the GalleryBananaMacAC ✓129ms4128kbC++2014.3kb2024-11-11 18:25:302024-11-11 18:25:34

Judging History

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

  • [2024-11-11 18:25:34]
  • 评测
  • 测评结果:AC
  • 用时:129ms
  • 内存:4128kb
  • [2024-11-11 18:25:30]
  • 提交

answer

/**
 * 10:43:50 11/11/24
 * point_vis
 */
// ./ICPC/Geometry/OrganizedTemplates/point_vis.cpp
//#include "Point.cpp"
/**
 * 15:15:28 9/27/24
 * Point
 */
// ./ICPC/Geometry/OrganizedTemplates/Point.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define uint unsigned int
#define double long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define nl '\n'
#define all(v) v.begin(), v.end()
#define NO (cout << "NO" << nl);
#define YES (cout << "YES" << nl);
#define F first
#define S second
#define INF LONG_LONG_MAX
#define MOD 1000000007ll
#define EPS 1e-9l
#define PI 3.14159265358979323846264338327950288L
#define pii pair<int, int>
#define X real()
#define Y imag()
#define vec vector
#define LT int T; cin >> T; while (T--)
template<typename T>
using vec2d = vector<vector<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using indexed_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

namespace Geometry {
    using ftype = double;
    using atype = double;
    const double eps = 1e-9l;
    const double pi = acos(-1.0l);
    const double e = exp(1.0L);
    const double inf = INF;
    const int iinf = LONG_LONG_MAX;
    const int prec = 25;

    ftype sqr(ftype v) { return v * v; }

    void setPrec(ostream& out = cout) {
        out << fixed << setprecision(prec);
    }

    //bool eq(const ftype& a, const ftype& b) {
    //    return a == b;
    //}
    bool eq(const ftype& a, const ftype& b) {
        return abs(a - b) < eps;
    }

    //bool ls(const ftype& a, const ftype& b) {
    //    return a < b;
    //}
    bool ls(const ftype& a, const ftype& b) {
        return (b - a) > eps;
    }

    //bool lse(const ftype& a, const ftype& b) {
    //    return a <= b;
    //}
    bool lse(const ftype& a, const ftype& b) {
        return ls(a, b) or eq(a, b);
    }

    //bool gt(const ftype& a, const ftype& b) {
    //    return a > b;
    //}
    bool gt(const ftype& a, const ftype& b) {
        return not ls(a, b) and not eq(a, b);
    }

    // Returns angle with respect to the x-axis.
    atype angle(atype x, atype y) {
        return atan2(y, x);
    }
    atype torad(atype a) { return a / 180 * pi; }
    atype todeg(atype a) { return a / pi * 180; }

    int sign(const ftype& v) {
        if (ls(0, v)) return 1;
        else if (ls(v, 0)) return -1;
        return 0;
    }

    // Orientation of 3 points forming an angle
    enum class Orientation {
        l = 1,
        r = -1,
        c = 0
    };

    // 2D point
    struct P {
        ftype x, y;
        static P polar(const ftype& r, const atype& a) {
            return {r * cos(a), r * sin(a)};
        }
        P(): x{0}, y{0} {}
        P(ftype x, ftype y): x{x}, y{y} {}
        explicit P(const complex<ftype>& p): P(p.real(), p.imag()) {}
        explicit P(const pair<ftype, ftype>& p): P(p.F, p.S) {}
        P(const P& p): P(p.x, p.y) {}
        explicit operator complex<ftype>() const {
            return {x, y};
        }
        explicit operator pair<ftype, ftype>() const {
            return {x, y};
        }
        ftype dist(const P& p) const {
            return (*this - p).abs();
        }
        atype r() const {
            return hypot(x, y);
        }
        atype a() const {
            return angle(x, y);
        }
        atype ua(const P& p) const {
            // undirected angle
            double v0 = fabs(a() - p.a()), v1 = fabs(p.ap() - ap());
            if (ls(v0, v1)) return v0;
            else return v1;
        }
        atype ap() const {
            atype res = angle(x, y);
            if (res < 0) res += 2 * pi;
            return res;
        }
        P operator-() const {
            return *this * -1;
        }
        P operator+() const {
            return *this;
        }
        P operator+=(const P& p) {
            x += p.x;
            y += p.y;
            return *this;
        }
        P operator-=(const P& p) {
            x -= p.x;
            y -= p.y;
            return *this;
        }
        P operator*=(const ftype& v) {
            x *= v;
            y *= v;
            return *this;
        }
        P operator/=(const ftype& v) {
            x /= v;
            y /= v;
            return *this;
        }
        P operator%=(const ftype& v) {
            x = fmod(x, v);
            y = fmod(y, v);
            return *this;
        }
        P operator^=(const ftype& an) {
            return *this = rotateccw(an);
        }
        P operator|=(const ftype& an) {
            return *this = rotatecw(an);
        }
        P operator|(const ftype& an) {
            P res = *this;
            res |= an;
            return res;
        }
        P operator^(const ftype& an) {
            P res = *this;
            res ^= an;
            return res;
        }
        P operator+(const P& p) const {
            P res = *this;
            res += p;
            return res;
        }
        P operator-(const P& p) const {
            P res = *this;
            res -= p;
            return res;
        }
        P operator*(const ftype& v) const {
            P res = *this;
            res *= v;
            return res;
        }
        P operator/(const ftype& v) const {
            P res = *this;
            res /= v;
            return res;
        }
        P operator%(const ftype& v) const {
            P res = *this;
            res %= v;
            return res;
        }
        bool operator==(const P& p) const {
            return eq(x, p.x) and eq(y, p.y);
        }
        bool operator<(const P& p) const {
            return eq(p.x, x) ? ls(y, p.y) : ls(x, p.x);
        }
        bool operator<=(const P& p) const {
            return *this < p or *this == p;
        }
        ftype cross(const P& b, const P& c) const {
            return (b - *this).cross(c - *this);
        }
        Orientation orientation(const P& pb, const P& pc) const {
            const P& pa = *this;
            ftype d = (pb - pa).cross(pc - pa);
            return static_cast<Orientation>(
                    ls(0, d) - ls(d, 0)
            );
        }
        ftype cross(const P& p) const {
            return x * p.y - y * p.x;
        }
        ftype dot(const P& p) const {
            return x * p.x + y * p.y;
        }
        ftype norm() const {
            return dot(*this);
        }
        atype abs() const {
            return sqrt((atype)norm());
        }
        P truncate(ftype v) const {
            // returns a vector with norm v and having same direction
            ftype k = abs();
            if (sign(k) == 0) return *this;
            v /= k;
            return {x * v, y * v};
        }
        P normalize() const {
            return truncate(1);
        }
        P normal_l() const {
            return {-y, x};
        }
        P normal_r() const {
            return {y, -x};
        }
        P rotateccw(const atype& angle, const P& ref = {0, 0}) const {
            P res;
            ftype xs = x - ref.x, ys = y - ref.y;
            res.x = ref.x + (xs * cos(angle) - ys * sin(angle));
            res.y = ref.y + (xs * sin(angle) + ys * cos(angle));
            return res;
        }
        P rotatecw(const atype& angle, const P& ref = {0, 0}) const {
            return rotateccw(-angle, ref);
        }
        friend P operator*(const ftype& v, const P& p) {
            return p * v;
        }
        friend istream& operator>>(istream& in, P& p) {
            int xv, yv;
            in >> xv >> yv;
            p = P(xv, yv);
            return in;
        }
        friend ostream& operator<<(ostream& out, const P& p) {
            setPrec(out);
            return out << "(" << p.x << ", " << p.y << ")";
        }
    };

    // basic comparison functions
    auto angleCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.a(), p1.a());
    };
    auto radiusCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.r(), p1.r());
    };
    auto stdCmp = [](const P& p0, const P& p1) -> bool {
        return p0 < p1;
    };
    auto xCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.x, p1.x);
    };
    auto yCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.y, p1.y);
    };

    // Hash function
    struct p_hash {
        static __int128 splitmix128(__int128 x) {
            // gr = 0x9e3779b97f4a7c15f39cc0605cedc835
            // c0 = 0xbf58476d1ce4e5b9a3f7b72c1e3c9e3b
            // c1 = 0x94d049bb133111ebb4093822299f31d7
            __int128 gr = 0x9e3779b97f4a7c15, c0 = 0xbf58476d1ce4e5b9, c1 = 0x94d049bb133111eb;
            gr <<= 64;
            c0 <<= 64;
            c1 <<= 64;
            gr += 0xf39cc0605cedc835;
            c0 += 0xa3f7b72c1e3c9e3b;
            c1 += 0xb4093822299f31d7;
            x += gr;
            x = (x ^ (x >> 62)) * c0;
            x = (x ^ (x >> 59)) * c1;
            return x ^ (x >> 63);
        }

        size_t operator()(const P& p) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            __int128 x = (((__int128)p.x) << 64) | ((__int128)p.y);
            return splitmix128(x + FIXED_RANDOM);
        }
    };
}
using namespace Geometry;

//如果两个向量的叉积结果符号相反(一个为正,一个为负),则说明线段AC和线段AD在线段AB的两侧,即线段AC和线段AD相交。
double RayIntersect(const P& a, const P& b, const P& c, const P& d, int* sides = NULL) {
    double cp1 = (c-a).cross(b-a), cp2 = (d-a).cross(b-a);
    double dp1 = (c-a).dot(b-a), dp2 = (d-a).dot(b-a);
    if (sides) *sides = (cp1 < -eps || cp2 < -eps) + 2 * (cp1 > eps || cp2 > eps);//sides 0,1,2,3,如果两个线段相交,一定是3  1,2是ab直线穿过c或者d的情况
    if (cp1 < -eps && cp2 < -eps || cp1 > eps && cp2 > eps) return -1.0;//叉积结果同号,线段不相交
    return (abs(cp1) < eps && abs(cp2) < eps) ? 0 : (dp1*cp2-dp2*cp1)/(cp2-cp1);//a到交点的距离乘以ab长度
}

bool POnLine(const P& a, const P& b, const P& p) {
    double ln = (b-a).abs(), cp = (b-a).cross(p-a), dp = (b-a).dot(p-a);
    return abs(cp/ln) < eps && dp/ln > -eps && dp/ln < ln+eps;//cp=0 && 0<dp<ln^2
}

int32_t main(){
    int n;
    cin>>n;
    vector<P> polygon(n);
    P s,g;
    for (int i = 0; i < n; ++i) {
        cin>>polygon[i];
    }
    cin>>g>>s;
    vector<P> endpoints;
    //找指向每个顶点方向距离最近的intersecting边
    polygon.push_back(g);//g点方向也需要找
    for(auto p:polygon){
        vector<tuple<double,int>> intersections;//交点距离,遮挡面
        if((p-s).abs()<eps)continue;
        p=(p-s)/(p-s).abs()+s;
        //找出sculpture向各个顶点出发, 不被遮挡能走的最远距离maxd,即视野不被遮挡的区域的终点(在多边形的边上)
        for(int i=0;i<n;++i){
            int side=0;
            auto d= RayIntersect(s,p,polygon[i],polygon[(i+1)%n],&side);
            if(d>-eps)
                intersections.emplace_back(d,side);
        }
        ranges::sort(intersections);
        double maxd=0;
        int sides=0;
        for(auto [d,s]:intersections){
            maxd=d;
            sides|=s;
            if(sides==3)break;
        }
        endpoints.push_back(s+(p-s)*maxd);//从sculpture出发,沿着射线,视野不被遮挡的区域的终点(在多边形的边上)
        //计算顶点p2,到sculpture发出的穿过顶点i的射线,的距离,以及交点
        for(auto p2:polygon){
            auto ortho=P(s.y-p.y,p.x-s.x)*1e5;
            auto d= RayIntersect(s,p,p2,p2+ortho);
            if(d<-eps)
                d= RayIntersect(s,p,p2,p2-ortho);
            if(d>eps && d<maxd-eps)
                endpoints.push_back(s+(p-s)*d);
        }
    }
    polygon.pop_back();
    //dijkstra算法求最短长度
    vector<P> points(polygon.size()+2+endpoints.size());
    int i=0;
    points[i++]=g;
    for(auto p:polygon)points[i++]=p;
    points[i++]=s;
    for(auto p:endpoints)points[i++]=p;
    priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> que;
    vector<double> dist(points.size(),1e20);//从g到每个节点的最短路径长度
    que.emplace(0.0,0);//从0号guard的起始位置出发
    for(i=que.top().second;i<=n;i=que.top().second){
        auto d=que.top().first;
        assert(que.size());
        que.pop();
        if(d>=dist[i])continue;
        dist[i]=d;
        for(int j=0;j<points.size();++j){
            if(i==j)continue;
            auto p1=points[i], p2=points[j];
            auto ln=(p1-p2).abs();
            if(ln<eps ||
               //如果j在poly顶点i关联的两条poly边上,可以直接沿着poly边走到j,不需要后面的包含性判断
               i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i) % n], p2) ||
               i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i + n - 2) % n], p2)) {
                que.emplace(d+ln,j);
                continue;
            }
            //判断p1p2是否被poly完全包含
            bool fullContained=true;
            p2=p1+(p2-p1)/ln;
            for(int k=0;k<polygon.size();++k){
                auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
                if(rd>eps && rd<ln-eps) {
                    fullContained=false;
                    break;
                }
            }
            if(!fullContained)continue;
            //判断一下p1p2上任意一点是不是在poly内部,来保证p1p2全段都在poly内部。通过p1p2中点画一任意射线, 看穿过poly为奇数还是偶数次
            int cnt=0;
            p1 = p1*2/3 + p2/ 3;
            p2 = p1 + P(cos(10), sin(10));
            for(int k=0;k<n;++k){
                auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
                cnt+=(rd>eps);
            }
            if(cnt%2==1)
                que.emplace(d+ln,j);
        }
    }
    setPrec();
    cout << que.top().first << nl;
}

詳細信息

Test #1:

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

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:

29.0000000000000000000000000

result:

ok found '29.0000000', expected '29.0000000', error '0.0000000'

Test #2:

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

input:

16
39 2
48 22
39 41
20 51
20 68
40 66
20 80
20 98
38 117
5 100
13 73
7 49
19 39
20 23
20 20
7 13
20 10
20 104

output:

13.0000000000000000000000000

result:

ok found '13.0000000', expected '13.0000000', error '0.0000000'

Test #3:

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

input:

16
13 33
20 60
23 66
39 97
49 105
73 166
100 205
117 272
98 216
80 180
66 172
68 156
51 122
41 121
22 92
2 44
10 40
104 228

output:

140.8722825824867501548487425

result:

ok found '140.8722826', expected '140.8722826', error '0.0000000'

Test #4:

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

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
81 12
33 23

output:

64.2045377025227085657221870

result:

ok found '64.2045377', expected '64.2045377', error '0.0000000'

Test #5:

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

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
33 23
81 12

output:

72.2834980411767275346179851

result:

ok found '72.2834980', expected '72.2834980', error '0.0000000'

Test #6:

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

input:

7
76 8
389 215
691 19
407 331
489 397
300 403
363 334
126 60
393 370

output:

6.6579177565105906165011940

result:

ok found '6.6579178', expected '6.6579178', error '0.0000000'

Test #7:

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

input:

3
0 1000
1000 0
1000 1000
567 578
589 601

output:

0.0000000000000015720538492

result:

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

Test #8:

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

input:

3
0 1000
0 0
1000 0
366 366
367 366

output:

0.0000000000000000000000000

result:

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

Test #9:

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

input:

5
50 93
278 178
199 300
596 362
208 519
421 388
142 153

output:

175.1697593917352965137146370

result:

ok found '175.1697594', expected '175.1697594', error '0.0000000'

Test #10:

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

input:

7
50 93
278 178
199 300
401 312
483 162
596 362
208 519
488 252
142 153

output:

289.6821398768899273878929534

result:

ok found '289.6821399', expected '289.6821399', error '0.0000000'

Test #11:

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

input:

8
10 10
40 25
20 25
20 35
12 23
30 23
10 20
5 40
15 15
19 26

output:

25.0000000000000000017347235

result:

ok found '25.0000000', expected '25.0000000', error '0.0000000'

Test #12:

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

input:

9
5 1000
6 3
5 999
0 1000
0 0
500 2
500 0
1000 0
1000 1000
1 4
993 1

output:

5.1010479069859044898294087

result:

ok found '5.1010479', expected '5.1010479', error '0.0000000'

Test #13:

score: 0
Accepted
time: 29ms
memory: 4020kb

input:

100
695 43
538 87
463 208
597 329
750 306
812 481
960 555
912 344
983 450
987 573
994 852
941 985
801 855
792 800
849 806
792 696
924 701
939 672
710 546
722 668
723 807
715 767
624 524
634 554
547 503
357 352
627 458
651 495
937 558
932 545
864 509
753 489
509 397
341 335
300 495
199 528
380 688
48...

output:

1695.1865730236420720666856710

result:

ok found '1695.1865730', expected '1695.1865730', error '0.0000000'

Test #14:

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

input:

20
840 854
839 45
996 905
959 938
852 938
730 423
425 493
136 481
213 778
527 740
691 941
22 830
83 313
462 155
636 21
462 321
360 324
238 422
402 492
806 406
952 822
410 838

output:

1424.3842014548487311387248155

result:

ok found '1424.3842015', expected '1424.3842015', error '0.0000000'

Test #15:

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

input:

74
89 395
52 622
124 832
115 698
95 598
199 491
190 356
191 398
132 315
94 371
34 221
91 0
153 139
220 465
260 283
312 30
409 15
338 50
343 52
437 69
359 89
332 213
377 505
375 396
405 199
657 90
658 50
360 50
618 23
642 7
824 191
688 417
795 227
709 286
662 321
646 175
485 210
381 357
420 329
441 3...

output:

2036.7557098766370524689506283

result:

ok found '2036.7557099', expected '2036.7557099', error '0.0000000'

Test #16:

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

input:

100
380 626
511 639
548 551
651 476
706 462
636 604
652 617
776 577
794 566
821 433
765 410
778 276
735 345
700 329
448 550
283 482
537 332
706 213
741 204
833 152
657 182
626 173
568 225
602 213
673 203
537 286
459 317
609 261
493 344
334 430
468 338
331 400
350 326
512 197
553 155
424 120
446 179
...

output:

307.8507108572825656522820026

result:

ok found '307.8507109', expected '307.8507109', error '0.0000000'

Test #17:

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

input:

100
425 641
614 667
719 714
598 761
548 727
505 713
415 832
505 856
724 762
764 767
803 755
773 727
826 633
832 509
842 570
829 456
742 430
706 513
604 527
942 208
912 569
959 330
975 605
977 878
882 609
844 694
869 789
930 896
992 894
763 937
699 930
701 854
732 810
709 820
657 881
507 896
342 805
...

output:

1941.5687357268885681049752634

result:

ok found '1941.5687357', expected '1941.5687357', error '0.0000000'

Test #18:

score: 0
Accepted
time: 110ms
memory: 4064kb

input:

100
845 528
842 889
837 997
809 663
786 746
793 554
782 470
769 798
709 992
520 993
95 983
191 897
250 666
136 715
139 745
32 979
32 918
5 916
0 740
31 283
10 238
36 177
102 740
141 635
145 353
132 435
106 607
130 383
41 66
139 12
403 11
330 45
225 48
153 216
251 342
233 374
289 424
266 99
334 62
34...

output:

1863.5717402634056304444598595

result:

ok found '1863.5717403', expected '1863.5717403', error '0.0000000'

Test #19:

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

input:

4
0 0
1000 0
1000 1000
0 1000
4 939
27 58

output:

0.0000000000000005354453806

result:

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

Test #20:

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

input:

94
5 5
995 5
995 995
5 995
990 990
5 990
970 970
5 970
950 950
5 950
930 930
5 930
910 910
5 910
890 890
5 890
870 870
5 870
850 850
5 850
830 830
5 830
810 810
5 810
790 790
5 790
770 770
5 770
750 750
5 750
730 730
5 730
710 710
5 710
690 690
5 690
670 670
5 670
650 650
5 650
630 630
5 630
610 610...

output:

620.2910607126302923175487081

result:

ok found '620.2910607', expected '620.2910607', error '0.0000000'

Test #21:

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

input:

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
70 30
70 10

output:

0.0000000000000000000000000

result:

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

Test #22:

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

input:

5
2 0
10 0
0 10
0 3
5 3
1 8
5 2

output:

5.0000000000000000000000000

result:

ok found '5.0000000', expected '5.0000000', error '0.0000000'

Test #23:

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

input:

5
2 0
10 0
0 10
0 3
5 3
1 4
5 2

output:

4.0000000000000000000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #24:

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

input:

12
0 0
2 0
2 4
1 4
1 5
2 5
2 7
0 7
0 3
1 3
1 2
0 2
1 6
1 1

output:

2.0000000000000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #25:

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

input:

10
0 0
2 0
2 4
1 4
2 5
2 7
0 7
0 3
1 2
0 2
1 6
1 1

output:

2.0000000000000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #26:

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

input:

12
0 0
2 0
3 3
5 0
6 3
7 0
8 2
7 6
5 2
4 6
2 2
0 2
1 1
7 1

output:

6.4787086646190748429226247

result:

ok found '6.4787087', expected '6.4787087', error '0.0000000'

Test #27:

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

input:

8
10 0
11 3
12 0
14 0
15 3
16 0
18 4
8 4
10 1
16 1

output:

5.8761229221400488333636181

result:

ok found '5.8761229', expected '5.8761229', error '0.0000000'

Test #28:

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

input:

8
10 0
11 3
12 0
16 3
14 0
17 0
17 4
8 4
10 1
15 1

output:

7.2360679774997896957638988

result:

ok found '7.2360680', expected '7.2360680', error '0.0000000'

Test #29:

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

input:

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
70 10
10 10

output:

58.1377674149945321210863902

result:

ok found '58.1377674', expected '58.1377674', error '0.0000000'

Test #30:

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

input:

11
0 0
4 0
4 1
5 1
5 0
7 0
7 2
3 2
3 1
2 2
0 2
6 1
1 1

output:

2.0000000000000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #31:

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

input:

3
31 41
59 26
53 58
36 41
56 31

output:

0.0000000000000000543054346

result:

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

Test #32:

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

input:

97
6 10
8 10
8 12
6 12
6 14
4 8
2 6
2 10
4 10
2 12
4 12
4 14
0 14
0 0
4 0
4 2
2 2
2 4
4 4
4 6
6 6
6 8
8 4
8 2
6 4
6 0
8 0
10 2
10 0
16 0
12 2
16 2
18 0
22 0
12 4
22 4
22 6
24 6
24 2
18 2
24 0
26 2
26 6
22 8
14 10
32 10
24 8
26 8
28 6
28 2
26 0
30 0
32 2
36 4
36 2
34 2
32 0
38 0
38 6
30 2
32 4
30 4
3...

output:

72.4810350801867537204326020

result:

ok found '72.4810351', expected '72.4810351', error '0.0000000'

Test #33:

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

input:

97
180 20
190 20
170 30
160 30
160 40
170 40
180 30
190 30
190 40
180 40
170 50
160 50
160 60
170 60
180 50
190 50
180 60
190 60
190 70
150 60
100 50
110 50
110 30
100 30
100 40
90 40
90 30
80 40
80 30
70 20
70 30
50 30
60 40
70 40
50 60
80 60
70 50
90 50
90 60
140 60
180 70
60 70
30 60
50 70
20 70
...

output:

240.4783856983092290571235594

result:

ok found '240.4783857', expected '240.4783857', error '0.0000000'

Test #34:

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

input:

89
10 15
10 10
5 10
5 15
0 15
0 0
5 0
5 5
15 5
10 0
100 0
20 5
25 5
15 10
85 10
30 5
90 5
105 0
285 0
295 5
350 5
290 0
445 0
355 5
380 5
450 0
735 0
715 5
665 5
710 10
730 10
720 5
735 5
740 0
745 0
740 5
745 5
745 15
740 10
735 10
740 15
685 15
705 10
630 10
660 5
590 5
610 10
625 10
680 15
615 15...

output:

306.4578983362806122725530145

result:

ok found '306.4578983', expected '306.4578983', error '0.0000000'

Test #35:

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

input:

94
5 5
995 5
995 995
5 995
990 990
5 990
970 970
5 970
950 950
5 950
930 930
5 930
910 910
5 910
890 890
5 890
870 870
5 870
850 850
5 850
830 830
5 830
810 810
5 810
790 790
5 790
770 770
5 770
750 750
5 750
730 730
5 730
710 710
5 710
690 690
5 690
670 670
5 670
650 650
5 650
630 630
5 630
610 610...

output:

1306.7333316327398173850582452

result:

ok found '1306.7333316', expected '1306.7333316', error '0.0000000'

Test #36:

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

input:

100
1000 20
1 40
1000 60
1 80
1000 100
1 120
1000 140
1 160
1000 180
1 200
1000 220
1 240
1000 260
1 280
1000 300
1 320
1000 340
1 360
1000 380
1 400
1000 420
1 440
1000 460
1 480
1000 500
1 520
1000 540
1 560
1000 580
1 600
1000 620
1 640
1000 660
1 680
1000 700
1 720
1000 740
1 760
1000 780
1 800
...

output:

47913.5987375407170816288271453

result:

ok found '47913.5987375', expected '47913.5987375', error '0.0000000'

Test #37:

score: 0
Accepted
time: 89ms
memory: 4128kb

input:

100
0 0
1000 0
1000 1000
0 1000
0 3
998 2
998 998
2 998
2 5
996 4
996 996
4 996
4 7
994 6
994 994
6 994
6 9
992 8
992 992
8 992
8 11
990 10
990 990
10 990
10 13
988 12
988 988
12 988
12 15
986 14
986 986
14 986
14 17
984 16
984 984
16 984
16 19
982 18
982 982
18 982
18 21
980 20
980 980
20 980
20 23...

output:

46834.0056361912317512974368583

result:

ok found '46834.0056362', expected '46834.0056362', error '0.0000000'

Test #38:

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

input:

100
7 409
21 321
39 254
62 198
74 177
79 169
96 146
105 135
118 120
154 90
181 72
188 68
199 62
210 57
219 53
239 45
311 24
320 22
356 15
376 12
408 8
483 2
499 1
500 1
516 2
570 6
581 7
630 13
746 40
749 41
768 48
780 53
823 75
834 82
845 90
854 97
903 146
913 159
925 177
964 267
972 295
973 299
98...

output:

0.0000000000000365813537749

result:

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

Test #39:

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

input:

13
100 100
110 110
100 120
110 130
100 140
110 150
100 160
90 155
100 145
90 135
100 125
90 115
100 105
100 106
100 159

output:

34.0000000000000000000000000

result:

ok found '34.0000000', expected '34.0000000', error '0.0000000'

Test #40:

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

input:

13
100 100
110 90
120 100
130 90
140 100
150 90
160 100
155 110
145 100
135 110
125 100
115 110
105 100
106 100
159 100

output:

34.0000000000000000000000000

result:

ok found '34.0000000', expected '34.0000000', error '0.0000000'

Test #41:

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

input:

13
100 100
120 100
120 120
140 120
140 140
160 140
160 160
145 165
145 145
125 145
125 125
105 125
105 105
106 106
159 159

output:

48.0832611206852311505621778

result:

ok found '48.0832611', expected '48.0832611', error '0.0000000'

Test #42:

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

input:

13
100 100
100 120
80 120
80 140
60 140
60 160
40 160
35 145
55 145
55 125
75 125
75 105
95 105
94 106
41 159

output:

48.0832611206852315530180242

result:

ok found '48.0832611', expected '48.0832611', error '0.0000000'

Test #43:

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

input:

100
7 409
21 321
39 254
62 198
74 177
79 169
96 146
105 135
118 120
154 90
181 72
188 68
199 62
210 57
219 53
239 45
311 24
320 22
356 15
376 12
408 8
483 2
499 1
500 1
516 2
570 6
581 7
630 13
746 40
749 41
768 48
780 53
823 75
834 82
845 90
854 97
903 146
913 159
925 177
964 267
972 295
981 335
99...

output:

467.0010706625842456518604706

result:

ok found '467.0010707', expected '467.0010707', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed