QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594292#4628. Driverless Car IICrysflyAC ✓5350ms5132kbC++146.1kb2024-09-27 21:01:422024-09-27 21:01:43

Judging History

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

  • [2024-09-27 21:01:43]
  • 评测
  • 测评结果:AC
  • 用时:5350ms
  • 内存:5132kb
  • [2024-09-27 21:01:42]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

typedef vector<int>vi;
#define fi first
#define se second
#define mkp make_pair
typedef pair<int,int>pii;
#define pb push_back

#define maxn 400005
#define inf 0x3f3f3f3f

mt19937_64 rnd(64);
#define db double
const db eps=1e-8,pi=3.14159265358979323;
int sgn(db x){
    return x<-eps?-1:x>eps;
}
int cmp(db a,db b){
    return sgn(a-b);
}
struct P{
    db x,y;
    int id;
    P(db xx=0,db yy=0){
        x=xx,y=yy;
    }
    P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
    P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
    P&operator *=(db o){return x*=o,y*=o,*this;}
    P&operator /=(db o){return x/=o,y/=o,*this;}

    friend P operator +(P a,P b){return a+=b;}
    friend P operator -(P a,P b){return a-=b;}
    friend P operator *(P a,db b){return a*=b;}
    friend P operator /(P a,db b){return a/=b;}

    friend db operator *(P a,P b){
        return a.x*b.y-a.y*b.x;
    }
    friend db operator %(P a,P b){
        return a.x*b.x+a.y*b.y;
    }
    P rot90(){
        swap(x,y),x=-x;
        return *this;
    }

    db len(){
        return sqrt(x*x+y*y);
    }
    db len2(){
        return x*x+y*y;
    }

    void print(){
        cout<<"("<<x<<","<<y<<")\n";
    }
};
db dis(P a,P b){
    return ((a-b)).len();
}
db cross(P a,P b,P c){
    return (b-a)*(c-a);
}

struct L{
    P a,b;
    int id;
    L(P aa,P bb){
        a=aa,b=bb;
        id=-1;
    }
    int in_sgn(P p){
        return sgn((b-a)*(p-a));
    }
    void print(){
        cout<<"("<<a.x<<","<<a.y<<")--("<<b.x<<","<<b.y<<")  "<<id<<"\n";
    }
};
P interl(P p1,P p2,P q1,P q2){
    db s1=cross(q1,q2,p1);
    db s2=-cross(q1,q2,p2);
    return (p1*s2+p2*s1)/(s1+s2);
}

P operator &(L a,L b){
    return interl(a.a,a.b,b.a,b.b);
}
int chksgn(L a,L b,L c){
    return c.in_sgn(a&b);
}
vector<L>cut(vector<L>&a,L l){
    vector<L>b;
    int n=a.size();
    For(i,0,n-1){
        L a1=a[i],a2=a[(i+1)%n],a3=a[(i+2)%n];
        int d1=chksgn(a1,a2,l);
        int d2=chksgn(a2,a3,l);
        if(d1>0 || d2>0 || (d1==0 && d2==0))b.pb(a2);
        if(d1>=0 && d2<0) b.pb(l);
    }
    return b;
}
L bisec(P a,P b){
    P o=(a+b)*0.5;
    return L(o,o+((b-a).rot90()));
}
vector<vector<L> > vor(vector<P>a){
    int n=a.size();
    auto b=a;
    const db U=1e5;
    vector<L>all;
    all.pb(L(P(-U,-U),P(U,-U)));
    all.pb(L(P(U,-U),P(U,U)));
    all.pb(L(P(U,U),P(-U,U)));
    all.pb(L(P(-U,U),P(-U,-U)));
    vector<vector<L> > res;
    For(i,0,n-1) res.pb(all);
    For(i,0,n-1){
        for(auto x:b){
            if(dis(x,a[i])>eps){
                L tmp=bisec(a[i],x);
                tmp.id=x.id;
             //   cout<<"cut "<<i<<" "<<x.id<<"\n";
             //   tmp.print();
                res[i]=cut(res[i],tmp);
            }
        }
    }
    return res;
}


struct cir{
    P o;
    db r;
    cir(P oo=P(0,0),db rr=0.0){
        o=oo,r=rr;
    }
};

db rad(P a,P b){
    return atan2l(a*b,a%b);
}

vector<P>operator &(cir a,L b){
    if(cmp(abs(((a.o-b.a)*(b.b-b.a))/dis(b.a,b.b)),a.r)>0) return {};
	db x=(b.a-a.o)%(b.b-b.a);
	db y=(b.b-b.a).len2();
	db d=x*x-y*((b.a-a.o).len2()-a.r*a.r);
	d=max(d,(db)0.0);
	P m=b.a-(b.b-b.a)*(x/y);
	P dr=(b.b-b.a)*(sqrt(d)/y);
	return {m-dr,m+dr};
}

db areaCT(db r,P p1,P p2){
	vector<P>is=(cir(P(0,0),r)&(L(p1,p2)));
	if(!is.size()) return r*r*rad(p1,p2)/2;
	bool b1=(cmp(p1.len2(),r*r)>0), b2=(cmp(p2.len2(),r*r)>0);
	if(b1&&b2){
		if(sgn((p1-is[0])%(p2-is[0]))<=0) 
			return (r*r*(rad(p1,is[0])+rad(is[1],p2))+(is[0]*is[1]))/2;
		return r*r*rad(p1,p2)/2;
	}
	if(b1) return (r*r*rad(p1,is[0])+is[0]*p2)/2;
	if(b2) return (p1*is[1]+r*r*rad(is[1],p2))/2;
	return (p1*p2)/2;
}

db solve(cir t,vector<P>a){
    db res=0;
    For(i,0,(int)a.size()-1){
        res+=areaCT(t.r,(a[i]-t.o),(a[(i+1)%a.size()]-t.o));
    }
    return res;
}

int n;
db k;
vector<P>a;

db res;

signed main()
{
//    P p=P(1,1);
//    p=p*0.5;
//    p.print();
    cin>>n>>k;
    a.resize(n);
    For(i,0,n-1)cin>>a[i].x>>a[i].y;
    shuffle(a.begin(),a.end(),rnd);
    For(i,0,n-1) a[i].id=i;
    vector<vector<L> > vd=vor(a);
 //   cout<<"QAQ\n"; return 0;
    For(i,0,n-1){
        auto v=vd[i];
        int m=v.size();
        For(qwq,0,m-1){

            int u=v[qwq].id;
          //  v[qwq].print();

            if(u==i || u<0) continue;
            // (i,u)
         //   cout<<"work "<<i<<" "<<u<<"\n";
            auto g=v;
            For(k,0,n-1)
                if(k!=i && k!=u){
                    L tmp=bisec(a[u],a[k]);
                    g=cut(g,tmp);
                }
            if(!g.size()) continue;

            db ds=dis(a[i],a[u]);
            if(ds>=k) continue;

            P o=(a[i]+a[u])*0.5;

            db A = k/2;
            P dx=(a[u]-a[i])/ds*A;
            P ddy=dx,dy=P(0,0);
            ddy.rot90();
            
            db rat=0;
			
			db leny=sqrt((k/2)*(k/2)-(ds/2)*(ds/2));
			dy=ddy/ddy.len()*leny;
		//	cout<<dy.x<<" "<<dy.y<<"\n";
			
        //    dx.print();
       //     dy.print();

            rat=dx.len()/dy.len();
            cir cr;
            cr.o=P(0,0);
            cr.r=dy.len();
            
            dx/=dx.len();
            dy/=dy.len();
          //  cout<<"rat "<<rat<<"\n";
          //  cout<<"dx: ";dx.print();
          //  cout<<"dy: ";dy.print();
            
            vector<P>cv;
           // cout<<"cir "<<dy.len()<<"\n";
            For(k,0,(int)g.size()-1) {
                P p=(g[k]&g[(k+1)%g.size()]);
           //     cout<<"p: "<<p.x<<" "<<p.y<<"\n";
                p=p-o;
                P t=P(p%dx,p%dy);
                t.x/=rat;
           //     cout<<"t: "<<t.x<<" "<<t.y<<"\n";
                cv.pb(t);
            }
            
            db ans=solve(cr,cv);
            res+=ans*rat;
         //   cout<<"ans "<<(ans*rat)<<"\n";
        }
    }
    printf("%.12lf",res);
	return 0;
}

/*
3 10
0 0
0 5
5 5

5 75
0 0
170 0
140 30
60 30
0 70
*/

详细

Test #1:

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

input:

5 75
0 0
170 0
140 30
60 30
0 70

output:

7881.133252266587

result:

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

Test #2:

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

input:

5 40
0 0
170 0
140 30
60 30
0 100

output:

0.000000000000

result:

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

Test #3:

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

input:

5 30000
0 0
1 2
1 5
0 2
0 1

output:

706960618.428099393845

result:

ok found '706960618.4280994', expected '706960618.4280993', error '0.0000000'

Test #4:

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

input:

5 101
0 0
170 0
140 30
60 30
0 100

output:

18147.517563393700

result:

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

Test #5:

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

input:

5 4
0 0
1 2
1 5
0 2
0 1

output:

22.871235881776

result:

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

Test #6:

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

input:

2 1
0 0
1 1

output:

0.000000000000

result:

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

Test #7:

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

input:

2 2
0 0
1 1

output:

2.221441469079

result:

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

Test #8:

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

input:

2 30000
-10000 10000
10000 -10000

output:

235619449.019234508276

result:

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

Test #9:

score: 0
Accepted
time: 3987ms
memory: 5100kb

input:

1982 30000
-2352 -9719
-2336 -9723
-2233 -9748
-2030 -9792
-2005 -9797
-2000 -9798
-1923 -9813
-1827 -9832
-1630 -9866
-1599 -9871
-1479 -9890
-1468 -9892
-1397 -9902
-1250 -9922
-1424 -9898
-1199 -9928
-950 -9955
-882 -9961
-832 -9965
-837 -9965
-805 -9968
-789 -9969
-808 -9967
-750 -9972
-747 -997...

output:

1963452789.211448669434

result:

ok found '1963452789.2114487', expected '1963452789.2114513', error '0.0000000'

Test #10:

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

input:

2000 30000
-9971 -8103
-9974 -7669
-9979 -8429
-9980 -8596
-9967 -6301
-9975 -6339
-9974 -5348
-9978 -4930
-9980 -5634
-9980 -5589
-9987 -5997
-9984 -5767
-9984 -5190
-9980 -5139
-9978 -4211
-9979 -4169
-9971 -2544
-9967 -2727
-9969 -2352
-9962 -1860
-9957 -579
-9963 -1432
-9962 -968
-9962 -674
-996...

output:

2302847929.375079631805

result:

ok found '2302847929.3750796', expected '2302847929.3750844', error '0.0000000'

Test #11:

score: 0
Accepted
time: 4011ms
memory: 5028kb

input:

2000 43
-2695 -9629
8195 5729
-9938 -1108
-9586 -2847
-9738 2271
8903 -4553
-2032 9791
-9923 1238
7294 6840
-9860 1663
3241 9459
-5277 -8493
-9646 -2633
-4653 8851
-257 9996
-387 -9992
-431 9990
-7092 7049
9357 3526
7863 -6177
5891 -8079
-7891 -6141
-1149 9933
-9619 2731
653 -9978
-2385 -9711
-2102 ...

output:

1118473.507343912032

result:

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

Test #12:

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

input:

2000 1000
-9998 -199
-6845 -7289
-8682 4961
-9442 3292
-9818 -1896
-8354 5495
5289 8486
1711 9852
5776 -8162
4571 -8893
-249 -9996
3805 -9247
-7979 6027
-9834 -1812
9895 1444
-9367 3499
-616 -9980
7589 6511
5186 -8549
9452 3263
9998 -167
9425 3339
4621 8868
9999 128
9852 -1709
-36 9999
7816 6236
-55...

output:

62718830.477509208024

result:

ok found '62718830.4775092', expected '62718830.4775094', error '0.0000000'

Test #13:

score: 0
Accepted
time: 4073ms
memory: 5076kb

input:

2000 5007
-9413 -3375
9379 3467
-9723 -2334
4422 8969
429 9990
-8665 4990
9649 -2622
-2849 -9585
9178 3968
-9127 -4085
-6548 -7557
-9078 -4193
7326 6806
8394 -5435
9995 -314
-1123 -9936
-6061 -7953
4007 9161
1869 -9823
7736 -6335
-3698 -9290
-7445 -6675
6589 -7522
-6779 7350
9552 2958
2878 -9576
-24...

output:

314563099.805489778519

result:

ok found '314563099.8054898', expected '314563099.8054886', error '0.0000000'

Test #14:

score: 0
Accepted
time: 3998ms
memory: 5032kb

input:

2000 9909
-8481 -5297
1607 -9869
-9017 4322
99 9999
7923 -6100
327 -9994
-7678 -6405
8277 5610
-4849 8745
9450 -3267
-5397 8417
-9999 -135
-9999 114
9633 -2683
4529 -8915
3547 -9349
3587 9334
7849 6195
-9957 920
-4897 -8718
-2880 9576
-9115 -4112
-5067 8620
-4321 -9018
184 9998
5751 8180
86 9999
809...

output:

622562129.837826848030

result:

ok found '622562129.8378268', expected '622562129.8378246', error '0.0000000'

Test #15:

score: 0
Accepted
time: 3984ms
memory: 5044kb

input:

2000 10001
-9701 2424
5769 8167
6540 7564
-9502 -3115
-9992 399
-1243 9922
3450 9385
-4982 8670
-9274 -3739
2691 -9630
-9959 894
-606 -9981
-8090 5877
9999 -34
2126 -9771
-8672 4978
-8374 5465
3424 9395
-3361 -9418
-9111 -4120
-4226 9062
9257 3780
8454 5341
4260 -9046
-8931 4497
-9816 1907
-4175 -90...

output:

706839355.671282887459

result:

ok found '706839355.6712829', expected '706839355.6712799', error '0.0000000'

Test #16:

score: 0
Accepted
time: 4089ms
memory: 5016kb

input:

2000 10106
-78 9999
-2862 -9581
9965 827
9261 3771
-4809 8767
-9789 -2039
97 9999
8761 -4821
-2243 9745
836 9964
-598 9982
9940 1091
7987 -6017
-6487 -7609
-9200 -3917
-9707 2402
8605 -5093
1685 -9856
-406 9991
-5236 -8519
-1854 9826
-2039 9789
9085 -4177
-532 -9985
776 -9969
-209 9997
7024 -7117
-1...

output:

711795947.662431478500

result:

ok found '711795947.6624315', expected '711795947.6624339', error '0.0000000'

Test #17:

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

input:

2000 30000
-243 -9997
-6233 -7819
-8785 4777
1422 9898
9979 -645
5567 -8306
1676 -9858
-8679 4967
9947 -1027
-2643 9644
4383 8987
-5826 -8127
-2309 9729
-9116 -4109
7867 6173
9357 3525
3887 -9213
-8025 -5965
1930 -9811
-9275 -3735
9994 327
-9831 -1825
-3950 9186
-229 9997
-4634 -8861
-5735 -8191
414...

output:

1963404849.899137973785

result:

ok found '1963404849.8991380', expected '1963404849.8991411', error '0.0000000'

Test #18:

score: 0
Accepted
time: 5181ms
memory: 4716kb

input:

2000 1000
8891 8891
6955 6955
4920 4920
-4006 -4006
-5341 -5341
-9888 -9888
-9028 -9028
-7032 -7032
-115 -115
3247 3247
-5885 -5885
-6716 -6716
-1992 -1992
865 865
-6939 -6939
-461 -461
-5705 -5705
-7859 -7859
5401 5401
-5787 -5787
-1791 -1791
-9180 -9180
8901 8901
2374 2374
-9585 -9585
4684 4684
-6...

output:

29024838.678556069732

result:

ok found '29024838.6785561', expected '29024838.6785562', error '0.0000000'

Test #19:

score: 0
Accepted
time: 5325ms
memory: 4684kb

input:

2000 10000
5498 5498
2338 2338
-7237 -7237
-4384 -4384
2337 2337
-5016 -5016
5752 5752
-6674 -6674
2008 2008
9623 9623
1509 1509
6905 6905
-5705 -5705
-1389 -1389
-3881 -3881
4521 4521
3037 3037
9056 9056
3320 3320
-6374 -6374
874 874
5713 5713
-9651 -9651
-3633 -3633
7335 7335
-1143 -1143
7652 7652...

output:

360801547.034468770027

result:

ok found '360801547.0344688', expected '360801547.0344678', error '0.0000000'

Test #20:

score: 0
Accepted
time: 5172ms
memory: 4684kb

input:

2000 15000
-9624 -9624
8301 8301
658 658
7304 7304
6640 6640
-2186 -2186
-481 -481
4953 4953
-8017 -8017
9522 9522
-4614 -4614
-4396 -4396
4236 4236
-4151 -4151
-4505 -4505
2911 2911
4839 4839
-1971 -1971
2636 2636
5379 5379
-5523 -5523
-2430 -2430
-715 -715
9063 9063
-3791 -3791
655 655
-3966 -3966...

output:

666125609.511438727379

result:

ok found '666125609.5114387', expected '666125609.5114413', error '0.0000000'

Test #21:

score: 0
Accepted
time: 5350ms
memory: 4704kb

input:

2000 20000
7893 7893
47 47
4934 4934
-8512 -8512
2709 2709
7948 7948
6471 6471
5646 5646
-6086 -6086
-5469 -5469
3581 3581
-6782 -6782
6259 6259
7366 7366
6534 6534
-4861 -4861
-3491 -3491
-9201 -9201
-2845 -2845
1563 1563
-6070 -6070
-7882 -7882
8388 8388
8062 8062
-4559 -4559
88 88
8539 8539
-5210...

output:

1051229066.443222284317

result:

ok found '1051229066.4432223', expected '1051229066.4432192', error '0.0000000'

Test #22:

score: 0
Accepted
time: 5151ms
memory: 4696kb

input:

2000 30000
-559 -559
-2871 -2871
-7318 -7318
7054 7054
-9824 -9824
-2649 -2649
-186 -186
2690 2690
-8603 -8603
7658 7658
-9898 -9898
2157 2157
331 331
1434 1434
5545 5545
9048 9048
5417 5417
9655 9655
2199 2199
-1016 -1016
-2990 -2990
-555 -555
-8419 -8419
6892 6892
-2109 -2109
-4055 -4055
-2837 -28...

output:

1837047515.115791082382

result:

ok found '1837047515.1157911', expected '1837047515.1157992', error '0.0000000'

Test #23:

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

input:

3 109
0 0
100 0
0 100

output:

7178.765740686707

result:

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

Test #24:

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

input:

3 150
200 0
100 100
0 0

output:

11542.293917208644

result:

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

Test #25:

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

input:

3 59
50 50
100 50
100 100

output:

2691.498297977446

result:

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

Test #26:

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

input:

3 6
3 0
0 4
0 0

output:

36.677386534132

result:

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

Test #27:

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

input:

3 11833
10000 10000
-10000 10000
10000 9999

output:

109971363.267015501857

result:

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

Test #28:

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

input:

3 11851
10000 10000
-10000 10000
10000 9900

output:

110302261.260827332735

result:

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

Test #29:

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

input:

3 2594
10000 10000
9999 10000
10000 -10000

output:

5284815.043503535911

result:

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

Test #30:

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

input:

3 201
0 0
200 0
100 173

output:

9982.297803652069

result:

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

Test #31:

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

input:

3 104
0 0
200 0
100 1

output:

4642.759408104534

result:

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

Test #32:

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

input:

3 5785
-10000 -10000
10000 9999
9999 10000

output:

26284310.865447595716

result:

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

Test #33:

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

input:

4 13
10 10
20 10
20 20
10 20

output:

258.909401099599

result:

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

Test #34:

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

input:

4 23724
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

807728367.961906313896

result:

ok found '807728367.9619063', expected '807728367.9619061', error '0.0000000'

Test #35:

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

input:

4 143
100 0
200 100
100 200
0 100

output:

9482.926424850863

result:

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

Test #36:

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

input:

4 109
0 1
100 0
101 100
1 101

output:

13860.589293863228

result:

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

Test #37:

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

input:

4 52
0 0
100 0
100 50
0 50

output:

1166.643872536871

result:

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

Test #38:

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

input:

4 52
0 0
50 0
50 100
0 100

output:

1166.643872536871

result:

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

Test #39:

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

input:

4 35
0 10
10 0
100 90
90 100

output:

1760.150705629906

result:

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

Test #40:

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

input:

8 309
0 100
100 0
250 0
350 100
350 250
250 350
100 350
0 250

output:

288293.525002200156

result:

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

Test #41:

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

input:

6 65
0 50
10 0
70 0
80 10
70 50
50 80

output:

9724.725513831032

result:

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

Test #42:

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

input:

4 36
0 100
0 0
100 0
20 20

output:

629.699314290690

result:

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

Test #43:

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

input:

4 102
0 100
55 55
100 0
100 100

output:

13882.561312869959

result:

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

Test #44:

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

input:

8 92
0 0
100 0
100 20
40 20
40 40
100 40
100 60
0 60

output:

19558.178119534452

result:

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

Test #45:

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

input:

12 46
0 0
90 0
90 30
40 30
40 40
90 40
90 50
0 50
0 20
50 20
50 10
0 10

output:

8259.813836182804

result:

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

Test #46:

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

input:

12 129
0 0
100 0
100 100
10 100
10 110
200 110
200 60
101 60
101 40
210 40
210 120
0 120

output:

57423.870102366120

result:

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

Test #47:

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

input:

10 19
1000 0
1100 0
1200 100
1220 200
1200 110
1100 10
1000 10
900 110
880 200
900 100

output:

964.325669198451

result:

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

Test #48:

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

input:

16 21
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10

output:

2810.531813896071

result:

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

Test #49:

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

input:

8 25
0 1
100 0
5 5
200 5
105 0
205 1
205 10
0 10

output:

1689.504289107480

result:

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

Test #50:

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

input:

8 65
0 1
50 0
5 5
200 5
150 0
205 1
205 10
0 10

output:

9196.679964984673

result:

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

Test #51:

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

input:

9 73
99 100
100 100
99 99
301 99
300 100
301 100
201 274
200 273
199 274

output:

12766.671099716405

result:

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

Test #52:

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

input:

15 36
0 0
10 0
20 0
30 0
40 0
50 0
40 10
30 20
20 30
10 40
0 50
0 40
0 30
0 20
0 10

output:

4740.008045959009

result:

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

Test #53:

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

input:

11 12
0 0
100 0
90 5
80 10
70 15
60 20
50 25
40 20
30 15
20 10
10 5

output:

402.675532256994

result:

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

Test #54:

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

input:

8 28
0 0
20 30
0 60
0 50
0 40
0 30
0 20
0 10

output:

2051.433253676369

result:

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

Test #55:

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

input:

18 57
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 30
120 60
120 90
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

21479.626284501177

result:

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

Test #56:

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

input:

15 69
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

22668.012217610052

result:

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

Test #57:

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

input:

11 55
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120

output:

11579.138106407032

result:

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

Test #58:

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

input:

9 29
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
0 120

output:

2397.294227402404

result:

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

Test #59:

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

input:

29 14
0 0
100 0
100 50
0 50
0 20
80 20
80 30
10 30
10 40
20 40
30 40
40 40
50 40
60 40
70 40
80 40
90 40
90 30
90 20
90 10
80 10
70 10
60 10
50 10
40 10
30 10
20 10
10 10
0 10

output:

2203.792222313417

result:

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

Test #60:

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

input:

24 171
0 0
100 0
100 100
200 100
200 0
300 0
300 100
300 200
200 200
200 300
300 300
300 400
300 500
200 500
200 400
100 400
100 500
0 500
0 400
0 300
100 300
100 200
0 200
0 100

output:

261180.687556682213

result:

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

Test #61:

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

input:

4 62
50 50
100 50
100 101
50 100

output:

5737.571587696444

result:

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

Test #62:

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

input:

10 163
100 300
150 50
100 0
200 50
250 150
250 50
400 0
300 50
350 50
400 300

output:

64397.219847018408

result:

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

Test #63:

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

input:

10 110
300 400
50 350
50 300
0 400
50 250
150 250
50 200
0 100
50 150
300 100

output:

33550.690491449815

result:

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

Test #64:

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

input:

5 147
0 0
100 100
60 40
200 200
40 60

output:

30148.185655712532

result:

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

Test #65:

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

input:

5 93
0 0
100 100
60 40
120 120
40 60

output:

15528.961423700766

result:

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

Test #66:

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

input:

5 13
0 0
100 100
51 49
200 200
49 51

output:

129.552611453137

result:

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

Test #67:

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

input:

5 79
100 10
300 0
200 10
400 10
300 20

output:

4741.989366510033

result:

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

Test #68:

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

input:

5 121
20 300
10 400
10 200
0 300
10 100

output:

23546.305806071021

result:

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

Test #69:

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

input:

10 45
110 171
57 121
56 102
7 17
101 24
65 34
70 43
157 6
134 20
93 54

output:

6086.953520603193

result:

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

Test #70:

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

input:

28 40
90 55
160 20
323 47
418 138
371 386
367 225
321 305
306 115
284 436
281 216
233 86
231 227
219 312
216 405
213 45
184 92
182 345
168 462
155 275
136 107
106 211
100 159
94 308
85 232
62 413
43 160
0 338
16 95

output:

841.806151081243

result:

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

Test #71:

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

input:

100 5101
10000 0
9980 627
9921 1253
9822 1873
9685 2486
9510 3090
9297 3681
9048 4257
8763 4817
8443 5358
8090 5877
7705 6374
7289 6845
6845 7289
6374 7705
5877 8090
5358 8443
4817 8763
4257 9048
3681 9297
3090 9510
2486 9685
1873 9822
1253 9921
627 9980
0 10000
-627 9980
-1253 9921
-1873 9822
-2486...

output:

317036769.688101887703

result:

ok found '317036769.6881019', expected '317036769.6881022', error '0.0000000'

Test #72:

score: 0
Accepted
time: 187ms
memory: 4188kb

input:

500 5245
10000 0
9999 125
9996 251
9992 376
9987 502
9980 627
9971 753
9961 878
9949 1003
9936 1128
9921 1253
9904 1377
9886 1502
9866 1626
9845 1750
9822 1873
9798 1997
9772 2120
9745 2242
9716 2364
9685 2486
9653 2608
9620 2729
9585 2850
9548 2970
9510 3090
9470 3209
9429 3328
9387 3446
9343 3564
...

output:

329398168.552823960781

result:

ok found '329398168.5528240', expected '329398168.5528243', error '0.0000000'

Test #73:

score: 0
Accepted
time: 835ms
memory: 4296kb

input:

1000 11977
10000 0
9999 62
9999 125
9998 188
9996 251
9995 314
9992 376
9990 439
9987 502
9984 565
9980 627
9976 690
9971 753
9966 815
9961 878
9955 941
9949 1003
9943 1066
9936 1128
9928 1190
9921 1253
9913 1315
9904 1377
9895 1440
9886 1502
9876 1564
9866 1626
9856 1688
9845 1750
9834 1812
9822 18...

output:

752475152.986921310425

result:

ok found '752475152.9869213', expected '752475152.9869199', error '0.0000000'

Test #74:

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

input:

100 3513
5675 0
5096 320
9219 1164
6323 1206
5537 1421
7180 2332
8787 3479
8780 4131
6560 3606
6417 4072
7534 5474
7349 6079
5101 4790
5742 6115
4154 5021
4618 6356
3825 6027
2789 5073
3987 8472
2099 5301
2014 6198
1762 6862
1775 9307
858 6793
397 6323
0 6011
-498 7921
-654 5183
-1292 6776
-1406 547...

output:

291600436.086861789227

result:

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

Test #75:

score: 0
Accepted
time: 277ms
memory: 4280kb

input:

500 813
9861 0
6812 85
7520 189
7380 278
5178 260
7253 456
6724 507
7648 674
6898 695
5518 626
5005 632
9331 1298
4943 751
9438 1555
6461 1148
9637 1838
5312 1082
9406 2040
8241 1896
8053 1960
8715 2237
6398 1728
5037 1429
4855 1443
7371 2293
7768 2524
8513 2884
9057 3196
6740 2474
8789 3352
5730 22...

output:

116324442.332265764475

result:

ok found '116324442.3322658', expected '116324442.3322655', error '0.0000000'

Test #76:

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

input:

1000 1934
8091 0
9198 57
9060 113
5747 108
5479 137
6865 215
9352 352
7129 313
5012 252
5016 283
7401 465
8909 616
9970 753
9436 772
7619 671
5368 507
6896 695
8556 917
6143 697
6802 816
9764 1233
9025 1197
8619 1199
5442 792
8519 1294
8530 1351
8292 1366
8711 1492
9103 1618
8293 1528
6769 1291
9047...

output:

293082740.838980555534

result:

ok found '293082740.8389806', expected '293082740.8389802', error '0.0000000'

Test #77:

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

input:

100 3543
0 0
10000 0
10000 10000
9896 9853
9793 951
9690 1642
9587 4776
9484 6666
9381 5058
9278 8146
9175 6491
9072 714
8969 1675
8865 79
8762 3597
8659 4040
8556 1707
8453 8735
8350 6676
8247 8796
8144 2579
8041 2431
7938 3240
7835 827
7731 353
7628 5638
7525 1960
7422 7770
7319 8599
7216 5076
711...

output:

153098414.025734424591

result:

ok found '153098414.0257344', expected '153098414.0257345', error '0.0000000'

Test #78:

score: 0
Accepted
time: 281ms
memory: 4188kb

input:

500 2217
0 0
10000 0
10000 10000
9979 4349
9959 5502
9939 255
9919 639
9899 5248
9879 974
9859 7593
9839 1091
9818 5905
9798 6216
9778 8699
9758 9951
9738 2044
9718 8181
9698 5522
9678 1888
9657 7549
9637 9475
9617 3347
9597 136
9577 775
9557 2467
9537 1000
9517 3873
9496 1460
9476 4350
9456 7880
94...

output:

136330637.398092150688

result:

ok found '136330637.3980922', expected '136330637.3980920', error '0.0000000'

Test #79:

score: 0
Accepted
time: 1192ms
memory: 4568kb

input:

1000 867
0 0
10000 0
10000 10000
9989 4685
9979 9134
9969 1180
9959 3397
9949 6194
9939 3697
9929 7962
9919 1358
9909 5778
9899 6522
9889 6286
9879 2382
9869 41
9859 3865
9849 997
9839 1746
9829 8380
9819 8211
9809 6070
9799 5539
9789 7476
9779 4391
9769 4092
9759 9264
9749 2333
9739 3849
9729 6011
...

output:

107766545.053282082081

result:

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

Test #80:

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

input:

100 6560
-25 0
-24 0
-23 0
-22 0
-21 0
-20 0
-19 0
-18 0
-17 0
-16 0
-15 0
-14 0
-13 0
-12 0
-11 0
-10 0
-9 0
-8 0
-7 0
-6 0
-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
-9999 1
9999 2
-9999 3
9999 4
-9999...

output:

102310941.979648634791

result:

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

Test #81:

score: 0
Accepted
time: 180ms
memory: 4220kb

input:

500 3991
-125 0
-124 0
-123 0
-122 0
-121 0
-120 0
-119 0
-118 0
-117 0
-116 0
-115 0
-114 0
-113 0
-112 0
-111 0
-110 0
-109 0
-108 0
-107 0
-106 0
-105 0
-104 0
-103 0
-102 0
-101 0
-100 0
-99 0
-98 0
-97 0
-96 0
-95 0
-94 0
-93 0
-92 0
-91 0
-90 0
-89 0
-88 0
-87 0
-86 0
-85 0
-84 0
-83 0
-82 0
-...

output:

40481179.938956156373

result:

ok found '40481179.9389562', expected '40481179.9389558', error '0.0000000'

Test #82:

score: 0
Accepted
time: 880ms
memory: 4328kb

input:

1000 3490
-250 0
-249 0
-248 0
-247 0
-246 0
-245 0
-244 0
-243 0
-242 0
-241 0
-240 0
-239 0
-238 0
-237 0
-236 0
-235 0
-234 0
-233 0
-232 0
-231 0
-230 0
-229 0
-228 0
-227 0
-226 0
-225 0
-224 0
-223 0
-222 0
-221 0
-220 0
-219 0
-218 0
-217 0
-216 0
-215 0
-214 0
-213 0
-212 0
-211 0
-210 0
-20...

output:

33897196.084290094674

result:

ok found '33897196.0842901', expected '33897196.0842904', error '0.0000000'

Test #83:

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

input:

4 1431
0 0
2000 0
1500 866
500 866

output:

2901295.411570981145

result:

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

Test #84:

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

input:

4 1494
0 0
2000 0
1500 867
500 867

output:

3204485.262070733588

result:

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

Test #85:

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

input:

4 1354
0 0
1000 0
1500 866
1000 1732

output:

2526161.349072166253

result:

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

Test #86:

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

input:

4 1543
0 0
1000 0
1500 867
1000 1733

output:

3441791.104391602799

result:

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

Test #87:

score: 0
Accepted
time: 4206ms
memory: 4892kb

input:

2000 26184
-10000 9938
-10000 9914
-10000 9873
-10000 9831
-10000 9739
-10000 9710
-10000 9608
-10000 9595
-10000 9537
-10000 9524
-10000 9485
-10000 9470
-10000 9450
-10000 9428
-10000 9410
-10000 9376
-10000 9373
-10000 9321
-10000 9271
-10000 9245
-10000 9200
-10000 9027
-10000 9002
-10000 8959
-...

output:

1985529341.168380498886

result:

ok found '1985529341.1683805', expected '1985529341.1683798', error '0.0000000'

Test #88:

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

input:

4 17353
-10000 0
0 -10000
10000 0
0 10000

output:

447635977.903558254242

result:

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

Test #89:

score: 0
Accepted
time: 3113ms
memory: 4888kb

input:

2000 6251
-93 9907
-98 9902
-100 9900
-101 9899
-123 9877
-180 9820
-192 9808
-196 9804
-197 9803
-238 9762
-253 9747
-268 9732
-282 9718
-290 9710
-294 9706
-334 9666
-428 9572
-466 9534
-474 9526
-477 9523
-486 9514
-504 9496
-534 9466
-536 9464
-573 9427
-605 9395
-612 9388
-614 9386
-622 9378
-6...

output:

345070870.608154058456

result:

ok found '345070870.6081541', expected '345070870.6081530', error '0.0000000'

Test #90:

score: 0
Accepted
time: 178ms
memory: 4152kb

input:

500 1226
6426 -6946
6448 -6925
6471 -6903
6495 -6880
6520 -6856
6546 -6831
6573 -6805
6660 -6721
6691 -6691
6692 -6690
6722 -6659
6751 -6629
6779 -6600
6832 -6545
6881 -6494
6904 -6470
6947 -6425
6967 -6404
6986 -6384
7004 -6365
7021 -6347
7037 -6330
7052 -6314
7081 -6283
7122 -6239
7160 -6198
7172 ...

output:

19862863.536089595407

result:

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

Test #91:

score: 0
Accepted
time: 2332ms
memory: 4452kb

input:

2000 4433
-4 -6500
-3 -7000
0 -8000
1 -8000
4 -7000
5 -6500
6 -6000
7 -5000
8 -3000
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
9 21
9 22
9 23
9 24
9 25
9 26
9 27
9 28
9 29
9 30
9 31
9 32
9 33
9 34
9 35
9 36
9 37
9 38
9 39
9 40
9 41
9 42
9 43
9 44
9...

output:

87873437.299601212144

result:

ok found '87873437.2996012', expected '87873437.2996017', error '0.0000000'

Test #92:

score: 0
Accepted
time: 512ms
memory: 4296kb

input:

835 4479
-750 -9935
-731 -9937
-702 -9940
-692 -9941
-661 -9944
-640 -9946
-608 -9949
-597 -9950
-574 -9952
-562 -9953
-537 -9955
-524 -9956
-497 -9958
-483 -9959
-454 -9961
-439 -9962
-408 -9964
-392 -9965
-375 -9966
-357 -9967
-338 -9968
-318 -9969
-297 -9970
-275 -9971
-252 -9972
-228 -9973
-203 ...

output:

105230091.074271157384

result:

ok found '105230091.0742712', expected '105230091.0742711', error '0.0000000'

Test #93:

score: 0
Accepted
time: 2706ms
memory: 4684kb

input:

2000 12946
-5967 6
-5959 6
-5940 6
-5912 6
-5882 6
-5881 6
-5879 6
-5871 6
-5849 6
-5829 6
-5817 6
-5810 6
-5804 6
-5799 6
-5794 6
-5793 6
-5770 6
-5759 6
-5752 6
-5707 6
-5705 6
-5686 6
-5670 6
-5651 6
-5633 6
-5627 6
-5622 6
-5618 6
-5609 6
-5601 6
-5575 6
-5571 6
-5528 6
-5527 6
-5501 6
-5487 6
-...

output:

299525764.167798757553

result:

ok found '299525764.1677988', expected '299525764.1678017', error '0.0000000'

Test #94:

score: 0
Accepted
time: 416ms
memory: 4172kb

input:

1004 1020
1000 9
999 9
998 9
997 9
996 9
995 9
994 9
993 9
992 9
991 9
990 9
989 9
988 9
987 9
986 9
985 9
984 9
983 9
982 9
981 9
980 9
979 9
978 9
977 9
976 9
975 9
974 9
973 9
972 9
971 9
970 9
969 9
968 9
967 9
966 9
965 9
964 9
963 9
962 9
961 9
960 9
959 9
958 9
957 9
956 9
955 9
954 9
953 9
9...

output:

1997125.549366159132

result:

ok found '1997125.5493662', expected '1997125.5493661', error '0.0000000'

Test #95:

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

input:

183 18
-3 -4
-2 -8
-2 -7
-1 -7
-1 -8
0 -12
0 -6
-1 -6
-1 -4
0 -5
0 0
-1 -3
-1 0
-2 -6
-2 -3
-3 -2
-2 -2
-3 -1
-2 -1
-2 0
-12 0
-12 -1
-13 0
-15 0
-13 -1
-14 -1
-16 0
-16 -3
-15 -1
-13 -3
-14 -3
-13 -4
-15 -3
-15 -2
-16 -4
-16 -8
-15 -6
-15 -4
-14 -4
-12 -5
-13 -5
-12 -6
-12 -8
-13 -7
-13 -8
-12 -9
-...

output:

1049.875515212317

result:

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

Test #96:

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

input:

183 19
4 -3
8 -2
7 -2
7 -1
8 -1
12 0
6 0
6 -1
4 -1
5 0
0 0
3 -1
0 -1
6 -2
3 -2
2 -3
2 -2
1 -3
1 -2
0 -2
0 -12
1 -12
0 -13
0 -15
1 -13
1 -14
0 -16
3 -16
1 -15
3 -13
3 -14
4 -13
3 -15
2 -15
4 -16
8 -16
6 -15
4 -15
4 -14
5 -12
5 -13
6 -12
8 -12
7 -13
8 -13
9 -12
9 -13
7 -14
8 -14
8 -15
6 -14
6 -13
5 -1...

output:

1110.417662410084

result:

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

Test #97:

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

input:

183 18
-4 3
-8 2
-7 2
-7 1
-8 1
-12 0
-6 0
-6 1
-4 1
-5 0
0 0
-3 1
0 1
-6 2
-3 2
-2 3
-2 2
-1 3
-1 2
0 2
0 12
-1 12
0 13
0 15
-1 13
-1 14
0 16
-3 16
-1 15
-3 13
-3 14
-4 13
-3 15
-2 15
-4 16
-8 16
-6 15
-4 15
-4 14
-5 12
-5 13
-6 12
-8 12
-7 13
-8 13
-9 12
-9 13
-7 14
-8 14
-8 15
-6 14
-6 13
-5 14
-...

output:

1049.875515212317

result:

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

Test #98:

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

input:

183 18
3 4
2 8
2 7
1 7
1 8
0 12
0 6
1 6
1 4
0 5
0 0
1 3
1 0
2 6
2 3
3 2
2 2
3 1
2 1
2 0
12 0
12 1
13 0
15 0
13 1
14 1
16 0
16 3
15 1
13 3
14 3
13 4
15 3
15 2
16 4
16 8
15 6
15 4
14 4
12 5
13 5
12 6
12 8
13 7
13 8
12 9
13 9
14 7
14 8
15 8
14 6
13 6
14 5
16 9
16 10
15 12
16 11
16 16
12 16
13 15
13 14
...

output:

1049.875515212317

result:

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

Test #99:

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

input:

195 18
-14 -11
-13 -11
-13 -10
-14 -9
-14 -7
-15 -10
-15 -8
-14 -6
-13 -7
-13 -9
-12 -11
-12 -12
-11 -12
-11 -13
-10 -12
-10 -13
-9 -14
-9 -12
-8 -14
-7 -15
-6 -15
-8 -13
-7 -13
-8 -12
-7 -11
-8 -10
-8 -9
-6 -12
-7 -12
-6 -13
-4 -14
-6 -14
-5 -15
-8 -16
-5 -16
-4 -15
-4 -16
0 -16
0 -15
-3 -15
-1 -14...

output:

1044.148279694993

result:

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

Test #100:

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

input:

195 18
11 -14
11 -13
10 -13
9 -14
7 -14
10 -15
8 -15
6 -14
7 -13
9 -13
11 -12
12 -12
12 -11
13 -11
12 -10
13 -10
14 -9
12 -9
14 -8
15 -7
15 -6
13 -8
13 -7
12 -8
11 -7
10 -8
9 -8
12 -6
12 -7
13 -6
14 -4
14 -6
15 -5
16 -8
16 -5
15 -4
16 -4
16 0
15 0
15 -3
14 -1
13 -1
14 0
11 0
12 -1
9 -1
8 -2
8 -1
10 ...

output:

1044.148279694993

result:

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

Test #101:

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

input:

195 19
-11 14
-11 13
-10 13
-9 14
-7 14
-10 15
-8 15
-6 14
-7 13
-9 13
-11 12
-12 12
-12 11
-13 11
-12 10
-13 10
-14 9
-12 9
-14 8
-15 7
-15 6
-13 8
-13 7
-12 8
-11 7
-10 8
-9 8
-12 6
-12 7
-13 6
-14 4
-14 6
-15 5
-16 8
-16 5
-15 4
-16 4
-16 0
-15 0
-15 3
-14 1
-13 1
-14 0
-11 0
-12 1
-9 1
-8 2
-8 1...

output:

1104.793875199712

result:

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

Test #102:

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

input:

195 19
14 11
13 11
13 10
14 9
14 7
15 10
15 8
14 6
13 7
13 9
12 11
12 12
11 12
11 13
10 12
10 13
9 14
9 12
8 14
7 15
6 15
8 13
7 13
8 12
7 11
8 10
8 9
6 12
7 12
6 13
4 14
6 14
5 15
8 16
5 16
4 15
4 16
0 16
0 15
3 15
1 14
1 13
0 14
0 11
1 12
1 9
2 8
1 8
0 10
0 2
1 2
2 1
0 1
0 0
12 0
10 1
11 1
10 2
7 ...

output:

1104.793875199711

result:

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

Test #103:

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

input:

186 19
-13 -16
-12 -15
-12 -14
-13 -15
-15 -15
-15 -14
-14 -14
-13 -13
-14 -13
-14 -12
-13 -12
-12 -13
-13 -14
-11 -13
-9 -13
-8 -14
-11 -14
-11 -15
-12 -16
-6 -16
-10 -15
-7 -15
-5 -16
-2 -16
-5 -15
-6 -15
-7 -14
-6 -14
-4 -15
-3 -15
-4 -14
-4 -13
-2 -11
-1 -14
-1 -15
-2 -12
-2 -14
-3 -13
-3 -14
-1...

output:

1101.976380042344

result:

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

Test #104:

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

input:

186 21
16 -13
15 -12
14 -12
15 -13
15 -15
14 -15
14 -14
13 -13
13 -14
12 -14
12 -13
13 -12
14 -13
13 -11
13 -9
14 -8
14 -11
15 -11
16 -12
16 -6
15 -10
15 -7
16 -5
16 -2
15 -5
15 -6
14 -7
14 -6
15 -4
15 -3
14 -4
13 -4
11 -2
14 -1
15 -1
12 -2
14 -2
13 -3
14 -3
16 -1
16 0
8 0
10 -1
13 -1
7 -2
10 -2
11 ...

output:

1227.247523047190

result:

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

Test #105:

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

input:

186 18
-16 13
-15 12
-14 12
-15 13
-15 15
-14 15
-14 14
-13 13
-13 14
-12 14
-12 13
-13 12
-14 13
-13 11
-13 9
-14 8
-14 11
-15 11
-16 12
-16 6
-15 10
-15 7
-16 5
-16 2
-15 5
-15 6
-14 7
-14 6
-15 4
-15 3
-14 4
-13 4
-11 2
-14 1
-15 1
-12 2
-14 2
-13 3
-14 3
-16 1
-16 0
-8 0
-10 1
-13 1
-7 2
-10 2
-...

output:

1041.631315261508

result:

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

Test #106:

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

input:

186 18
13 16
12 15
12 14
13 15
15 15
15 14
14 14
13 13
14 13
14 12
13 12
12 13
13 14
11 13
9 13
8 14
11 14
11 15
12 16
6 16
10 15
7 15
5 16
2 16
5 15
6 15
7 14
6 14
4 15
3 15
4 14
4 13
2 11
1 14
1 15
2 12
2 14
3 13
3 14
1 16
0 16
0 8
1 10
1 13
2 7
2 10
3 11
3 9
5 11
6 11
7 12
5 12
4 11
4 12
5 13
6 1...

output:

1041.631315261508

result:

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

Test #107:

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

input:

191 19
-2 -3
-2 -2
-1 -2
0 -1
-3 -2
-5 -4
-5 -3
-4 -2
-6 -2
-8 -4
-9 -4
-9 -5
-8 -5
-7 -4
-7 -6
-6 -5
-6 -3
-5 -5
-4 -4
-3 -4
-5 -6
-6 -6
-6 -7
-8 -9
-7 -9
-3 -5
-2 -5
-4 -7
-2 -6
-1 -6
-1 -7
-2 -7
-2 -8
-1 -10
-2 -9
-1 -11
-3 -9
-4 -10
-3 -10
-2 -11
-3 -11
-3 -12
-1 -12
-1 -13
-3 -13
-1 -14
-1 -15
...

output:

1114.900416868521

result:

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

Test #108:

score: 0
Accepted
time: 33ms
memory: 4032kb

input:

191 18
3 -2
2 -2
2 -1
1 0
2 -3
4 -5
3 -5
2 -4
2 -6
4 -8
4 -9
5 -9
5 -8
4 -7
6 -7
5 -6
3 -6
5 -5
4 -4
4 -3
6 -5
6 -6
7 -6
9 -8
9 -7
5 -3
5 -2
7 -4
6 -2
6 -1
7 -1
7 -2
8 -2
10 -1
9 -2
11 -1
9 -3
10 -4
10 -3
11 -2
11 -3
12 -3
12 -1
13 -1
13 -3
14 -1
15 -1
14 -2
15 -3
15 -4
14 -3
13 -4
13 -6
14 -4
14 -5...

output:

1054.111750209564

result:

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

Test #109:

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

input:

191 18
-3 2
-2 2
-2 1
-1 0
-2 3
-4 5
-3 5
-2 4
-2 6
-4 8
-4 9
-5 9
-5 8
-4 7
-6 7
-5 6
-3 6
-5 5
-4 4
-4 3
-6 5
-6 6
-7 6
-9 8
-9 7
-5 3
-5 2
-7 4
-6 2
-6 1
-7 1
-7 2
-8 2
-10 1
-9 2
-11 1
-9 3
-10 4
-10 3
-11 2
-11 3
-12 3
-12 1
-13 1
-13 3
-14 1
-15 1
-14 2
-15 3
-15 4
-14 3
-13 4
-13 6
-14 4
-14 ...

output:

1054.111750209564

result:

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

Test #110:

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

input:

191 18
2 3
2 2
1 2
0 1
3 2
5 4
5 3
4 2
6 2
8 4
9 4
9 5
8 5
7 4
7 6
6 5
6 3
5 5
4 4
3 4
5 6
6 6
6 7
8 9
7 9
3 5
2 5
4 7
2 6
1 6
1 7
2 7
2 8
1 10
2 9
1 11
3 9
4 10
3 10
2 11
3 11
3 12
1 12
1 13
3 13
1 14
1 15
2 14
3 15
4 15
3 14
4 13
6 13
4 14
5 14
7 13
6 14
8 13
8 12
4 12
4 11
9 11
7 10
5 10
3 8
3 7
...

output:

1054.111750209564

result:

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

Test #111:

score: 0
Accepted
time: 2603ms
memory: 4788kb

input:

1759 65
19 19
20 21
20 20
21 21
21 20
22 20
23 19
24 17
24 18
25 18
25 17
27 18
29 18
30 19
30 22
29 20
26 20
29 19
28 19
26 18
24 19
27 19
24 20
23 20
21 22
23 22
23 21
24 21
25 20
25 21
26 21
25 22
24 22
25 23
25 24
24 23
20 23
22 24
20 24
22 25
19 25
19 27
21 28
22 29
24 29
23 28
24 28
25 29
24 3...

output:

12176.415784634308

result:

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

Test #112:

score: 0
Accepted
time: 2625ms
memory: 4720kb

input:

1717 63
26 39
27 41
25 41
26 43
23 43
24 42
24 41
23 39
21 40
23 40
23 41
22 41
23 42
22 42
22 44
24 44
24 45
19 45
21 44
20 44
21 43
20 43
20 42
19 42
19 44
15 45
18 45
23 46
26 46
26 45
25 45
25 44
26 44
27 45
28 45
27 44
28 44
28 43
27 43
26 42
30 42
29 43
31 43
33 44
31 44
33 45
30 44
29 44
32 4...

output:

11820.465003190360

result:

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

Test #113:

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

input:

83 303
0 164
1 197
1 150
0 163
0 65
1 100
1 41
0 64
0 25
1 40
1 2
0 24
0 10
1 1
0 9
0 0
2 0
2 59
1 101
1 149
2 60
2 165
1 216
1 238
2 166
2 470
1 462
1 535
2 471
2 771
1 651
1 714
2 772
2 861
1 831
1 900
2 862
2 907
1 901
1 911
2 908
2 957
1 912
1 983
2 958
2 999
0 999
0 997
1 998
1 987
0 996
0 993
...

output:

372903.194366242678

result:

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

Test #114:

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

input:

97 428
522 0
474 1
543 1
523 0
670 0
544 1
652 1
671 0
736 0
653 1
668 1
737 0
758 0
723 1
752 1
759 0
831 0
753 1
804 1
832 0
875 0
805 1
845 1
876 0
915 0
846 1
957 1
916 0
981 0
975 1
985 1
982 0
986 0
986 1
992 1
987 0
999 0
998 1
999 1
999 2
997 1
993 1
998 2
969 2
974 1
958 1
968 2
813 2
722 1...

output:

571148.974997022306

result:

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

Test #115:

score: 0
Accepted
time: 30ms
memory: 3996kb

input:

171 1000
3 40
2 61
2 48
1 53
1 56
2 62
2 71
1 57
1 67
2 102
2 72
3 41
3 146
2 161
2 193
3 147
3 165
2 194
2 219
1 257
1 298
2 220
2 249
3 166
3 196
2 299
2 250
1 380
1 413
2 426
2 300
3 197
3 304
2 427
2 529
3 305
3 547
2 565
2 530
1 414
1 453
2 566
2 572
1 454
1 586
2 662
2 573
3 548
3 707
2 663
2 ...

output:

1787797.082585362019

result:

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

Test #116:

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

input:

169 1000
292 1
223 0
460 0
447 1
496 1
461 0
510 0
497 1
528 1
511 0
650 0
632 1
614 1
573 2
602 2
633 1
653 1
651 0
841 0
837 1
846 1
806 2
869 2
847 1
872 1
842 0
899 0
873 1
917 1
900 0
912 0
928 1
918 1
901 2
956 2
929 1
995 1
913 0
999 0
996 1
995 2
997 2
997 1
999 1
999 2
998 2
999 3
996 3
994...

output:

1787889.165699039120

result:

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

Test #117:

score: 0
Accepted
time: 4580ms
memory: 4940kb

input:

2000 1161
3316 4595
4152 4662
4692 5559
4805 5785
4445 6103
3936 6224
4153 6375
4382 6574
4721 6189
6281 6497
5858 5760
6308 5713
6729 5979
6197 6721
6374 7103
6205 6871
5757 6512
5087 6488
5842 7042
4897 7761
5110 7282
4851 6381
4809 6715
4810 7013
4808 7440
3482 7551
3746 7800
3112 7468
3479 7039
...

output:

419757297.184556186199

result:

ok found '419757297.1845562', expected '419757297.1845574', error '0.0000000'

Test #118:

score: 0
Accepted
time: 4677ms
memory: 4984kb

input:

2000 155
-2720 -1363
-2774 1491
-2754 1837
-2751 4697
-2756 8857
-2915 9905
-2524 9530
-2774 9694
-2604 8757
-2541 1908
-2608 1807
-2650 3360
-2663 8316
-2640 -7601
-2644 -5216
-2672 -7637
-2673 8295
-2680 3413
-2707 9287
-2682 -5749
-2678 -8779
-3156 -9988
861 -9952
1509 -9829
1199 -9503
1342 -8775...

output:

4021264.634025147185

result:

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

Test #119:

score: 0
Accepted
time: 4615ms
memory: 4916kb

input:

1999 1266
389 180
389 168
363 119
380 137
375 139
451 124
404 140
453 147
541 133
492 206
483 188
499 256
572 138
571 199
608 165
573 25
554 45
546 72
502 54
520 83
539 130
459 83
437 103
454 57
428 60
439 77
420 74
421 83
422 108
418 106
396 124
406 82
418 59
372 88
356 52
363 35
402 46
422 52
420 ...

output:

6440404.454221410677

result:

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

Test #120:

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

input:

1998 4780
740 -650
753 -696
719 -663
683 -565
593 -539
586 -446
648 -415
713 -447
639 -331
566 -351
523 -297
575 -264
616 -286
541 -227
462 -324
460 -370
479 -380
585 -430
566 -427
510 -401
585 -516
489 -435
384 -380
423 -442
478 -536
379 -415
313 -361
325 -318
263 -421
303 -482
306 -512
287 -516
25...

output:

96030061.667105168104

result:

ok found '96030061.6671052', expected '96030061.6671051', error '0.0000000'

Test #121:

score: 0
Accepted
time: 4462ms
memory: 4984kb

input:

2000 17184
8596 -48
7794 130
7241 379
7079 -51
6516 146
6126 523
5542 402
6080 -117
6102 -221
5556 -714
6301 -699
6527 -264
6588 -1964
6638 -1591
6787 -1210
6613 -2173
7031 -1363
7158 -615
7338 -1411
7520 -1518
7412 -797
7297 -575
8579 -546
8285 -1447
8873 -845
9229 -2075
9066 -1543
8703 -2732
8751 ...

output:

1299273363.622246980667

result:

ok found '1299273363.6222470', expected '1299273363.6222489', error '0.0000000'

Test #122:

score: 0
Accepted
time: 4041ms
memory: 5112kb

input:

1982 2994
-2352 -9719
-2336 -9723
-2233 -9748
-2030 -9792
-2005 -9797
-2000 -9798
-1923 -9813
-1827 -9832
-1630 -9866
-1599 -9871
-1479 -9890
-1468 -9892
-1397 -9902
-1250 -9922
-1424 -9898
-1199 -9928
-950 -9955
-882 -9961
-832 -9965
-837 -9965
-805 -9968
-789 -9969
-808 -9967
-750 -9972
-747 -9972...

output:

281987464.994269549847

result:

ok found '281987464.9942695', expected '281987464.9942697', error '0.0000000'

Test #123:

score: 0
Accepted
time: 4542ms
memory: 4964kb

input:

2000 24944
-9971 -8103
-9974 -7669
-9979 -8429
-9980 -8596
-9967 -6301
-9975 -6339
-9974 -5348
-9978 -4930
-9980 -5634
-9980 -5589
-9987 -5997
-9984 -5767
-9984 -5190
-9980 -5139
-9978 -4211
-9979 -4169
-9971 -2544
-9967 -2727
-9969 -2352
-9962 -1860
-9957 -579
-9963 -1432
-9962 -968
-9962 -674
-996...

output:

1882969072.341686248779

result:

ok found '1882969072.3416862', expected '1882969072.3416920', error '0.0000000'