QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362008#8505. Almost Aligneducup-team2303#WA 5593ms19604kbC++202.6kb2024-03-23 13:53:262024-03-23 13:53:27

Judging History

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

  • [2024-03-23 13:53:27]
  • 评测
  • 测评结果:WA
  • 用时:5593ms
  • 内存:19604kb
  • [2024-03-23 13:53:26]
  • 提交

answer

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int> 
using namespace std;
inline int read(void) {
    int x=0,sgn=1; char ch=getchar();
    while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
    while(47<ch&&ch<58) {x=x*10+ch-48;   ch=getchar();}
    return sgn? x:-x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
    write((Ans%p+p)%p); pls
*/
#define double long double
int n;
double mid,Ans;
int x[1000006],y[1000006],vx[1000006],vy[1000006];
inline void chkmin(double&x,double y) { x=min(x,y); }
inline void chkmax(double&x,double y) { x=max(x,y); }
inline double check(double t) {
    double mix,mxx,miy,mxy;
    mix=mxx=x[1]+vx[1]*t;
    miy=mxy=y[1]+vy[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(mix,x[i]+vx[i]*t);
        chkmax(mxx,x[i]+vx[i]*t);
        chkmin(miy,y[i]+vy[i]*t);
        chkmax(mxy,y[i]+vy[i]*t);
    }
    // cerr<<"t = "<<t<<'|'<<mix<<' '<<mxx<<' '<<miy<<' '<<mxy<<endl;
    chkmin(Ans,(mxx-mix)*(mxy-miy));
    return (mxx-mix)*(mxy-miy);
}
inline double checkX(double t) {
    double mix,mxx;
    mix=mxx=x[1]+vx[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(mix,x[i]+vx[i]*t);
        chkmax(mxx,x[i]+vx[i]*t);
    }
    return mxx-mix;
}
inline double checkY(double t) {
    double miy,mxy;
    miy=mxy=y[1]+vy[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(miy,y[i]+vy[i]*t);
        chkmax(mxy,y[i]+vy[i]*t);
    }
    return (mxy-miy);
}
inline double checkmid(double t) {
    return abs(log(checkX(t))-log(checkY(t)));
}
inline void qmid(void) {
    double L=0,R=1000000000000;
    for(int t=0; t<=200; ++t) {
        double ml=(2*L+R)/3;
        double mr=(L+2*R)/3;
        if(checkmid(ml)<checkmid(mr)) R=mr;
        else L=ml;
    }
    mid=L;
}
inline void solve(double L,double R) {
    for(int t=0; t<=200; ++t) {
        double ml=(2*L+R)/3;
        double mr=(L+2*R)/3;
        if(check(ml)<check(mr)) R=mr;
        else L=ml;
    }
    check(L);
}
signed main() {
    // freopen("localinput","r",stdin);
    // freopen("localoutput","w",stdout);
    n=read(); Ans=1e27;
    for(int i=1; i<=n; ++i) x[i]=read(),y[i]=read(),vx[i]=read(),vy[i]=read();
    qmid();
    // cerr<<mid<<endl;
    solve(0,mid);
    solve(mid,1000000000.0);
    printf("%.12Lf\n",Ans);
    // fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.222222222222

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

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

input:

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

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

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

input:

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

output:

4.000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

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

input:

1
0 0 0 0

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

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

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000031.999952077866

result:

ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 5593ms
memory: 19596kb

input:

1000000
-871226 486657 -467526 31395
-65837 846554 469710 -907814
927993 -45099 713462 -276539
261942 483255 746021 811070
63449 -779486 588838 -413687
812070 -87868 -813499 -420768
112521 -622607 -832012 921368
-182120 517379 -401743 -837524
-685985 337832 643014 135144
12895 326935 -495720 930620
...

output:

3999996000000.000000000000

result:

ok found '3999996000000.000000000', expected '3999996000000.000000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 5578ms
memory: 19604kb

input:

1000000
3663 6989 -2671 9642
9904 -8111 -4995 5797
599 -8323 -9362 -9045
-6740 1530 3072 6531
3681 -6009 593 -7248
-7878 7266 -5191 4871
4007 -3346 -3801 -3512
192 4840 -4026 -1845
6224 -6143 -1857 5659
-5960 4616 9665 655
5532 -1324 -3901 351
-7670 3951 9243 -4678
2931 -115 -5127 -2353
-7500 -7221 ...

output:

400000000.000000000058

result:

ok found '400000000.000000000', expected '400000000.000000000', error '0.000000000'

Test #8:

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

input:

10
-1 19 -2 6
-26 4 -8 0
6 27 0 7
-3 9 -1 -4
4 -5 5 -5
30 -21 -7 6
-23 -6 0 -5
0 19 3 -5
19 -22 -6 -5
-5 9 -2 5

output:

2744.000000000000

result:

ok found '2744.000000000', expected '2744.000000000', error '0.000000000'

Test #9:

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

input:

10
-3 30 6 7
25 -7 -5 -6
21 8 8 6
-5 19 -6 -1
29 14 -4 -8
-18 15 -7 4
-1 -2 6 -4
-9 -23 -9 -10
-17 12 7 -6
28 16 -7 -4

output:

2491.000000000000

result:

ok found '2491.000000000', expected '2491.000000000', error '0.000000000'

Test #10:

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

input:

100
259 401 17 5
145 -361 -30 -7
397 314 23 -29
-53 332 -19 -5
-11 413 4 -29
-152 -336 1 -26
479 -7 17 -5
142 121 3 24
93 -424 6 -16
387 -138 20 6
136 99 3 -19
-168 181 5 -26
416 -259 26 -28
-108 328 -11 15
247 190 -16 0
-446 473 27 -20
-450 -116 3 -23
79 -409 4 -13
-192 184 -18 -27
50 22 23 -7
187 ...

output:

951042.036882807852

result:

ok found '951042.036882808', expected '951042.036882808', error '0.000000000'

Test #11:

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

input:

100
78 -474 17 -17
439 -473 2 -18
-81 -8 -23 14
405 363 -19 23
-85 491 -10 -11
130 433 -10 24
363 406 -26 -25
370 -110 29 -23
179 -354 -9 -14
155 -183 30 16
9 373 -17 -9
-376 486 16 -22
19 -221 15 -1
-449 253 27 19
-275 369 -17 13
-200 -412 -9 26
-184 -249 2 -25
103 -407 4 -20
326 28 -4 29
145 -101 ...

output:

985195.419501133787

result:

ok found '985195.419501134', expected '985195.419501134', error '0.000000000'

Test #12:

score: 0
Accepted
time: 563ms
memory: 12368kb

input:

100000
-967368 981728 -282756 336437
261266 269990 509802 144678
462067 -410569 -758751 -855049
-223324 236410 -518913 543981
830399 -945912 -925250 -799821
-708921 186464 583718 422275
-764681 -276675 -270713 155951
-736997 136674 155052 -266181
191391 -482614 -181940 748298
85598 963827 730561 168...

output:

3999878000858.000000476837

result:

ok found '3999878000858.000000000', expected '3999878000858.000000000', error '0.000000000'

Test #13:

score: 0
Accepted
time: 564ms
memory: 10408kb

input:

100000
735591 227533 -560510 -492634
151314 -955343 -798474 615112
-405134 -371377 72931 71513
995160 468797 39541 -692246
-412359 -48711 381217 49510
-33387 908154 -552594 -470470
893889 28395 -979649 -864267
-667790 324922 -645051 -356687
528418 -766919 496442 -133957
-667748 -194840 -961485 -8606...

output:

3999945328884.535295009613

result:

ok found '3999945328884.535156250', expected '3999945328884.535156250', error '0.000000000'

Test #14:

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

input:

4
1 1 -2 -3
-2 1 4 -5
4 -1 0 -2
-3 -4 -1 5

output:

10.484375000000

result:

ok found '10.484375000', expected '10.484375000', error '0.000000000'

Test #15:

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

input:

3
3 -1 5 -5
-1 1 -1 -4
0 4 -3 -5

output:

20.000000000000

result:

ok found '20.000000000', expected '20.000000000', error '0.000000000'

Test #16:

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

input:

1
2 -2 -1 -3

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #17:

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

input:

9
2 1 0 -5
1 3 4 0
-2 2 5 5
-5 -1 4 0
-5 -1 3 0
4 3 0 -3
4 -5 1 1
5 -1 -2 -5
2 -4 -2 1

output:

69.444444444444

result:

ok found '69.444444444', expected '69.444444444', error '0.000000000'

Test #18:

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

input:

3
-5 1 1 -4
-1 1 5 4
1 0 -2 0

output:

6.000000000000

result:

ok found '6.000000000', expected '6.000000000', error '0.000000000'

Test #19:

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

input:

3
485996 232438 356271 686535
316095 -82403 -663737 -892162
-301128 -973876 -705273 342014

output:

949518700936.000000119209

result:

ok found '949518700936.000000000', expected '949518700936.000000000', error '0.000000000'

Test #20:

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

input:

3
-307334 408041 -520618 -752353
-111541 -171569 622704 -397094
-856154 25489 -1939 897474

output:

431585140930.000000000000

result:

ok found '431585140930.000000000', expected '431585140930.000000000', error '0.000000000'

Test #21:

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

input:

4
554523 -843525 434069 -518131
910677 518840 -857480 -612229
231960 965891 333430 -440474
-687304 726302 164236 659483

output:

2493690369944.078348159790

result:

ok found '2493690369944.078125000', expected '2493690369944.078125000', error '0.000000000'

Test #22:

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

input:

4
269831 -364179 -591251 516327
-578364 795567 -872538 -766732
-896806 -70577 -998004 159063
-962947 -103040 -47465 -189048

output:

577576180387.100443542004

result:

ok found '577576180387.100463867', expected '577576180387.100463867', error '0.000000000'

Test #23:

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

input:

10
-120900 371317 -965845 999010
105720 -738865 -573556 47269
959567 790508 -501437 -94217
900701 822342 916298 873194
351985 737907 523995 486812
224233 -197678 -958739 -157846
-571724 -329927 757807 -207627
-88478 -130810 866209 -314752
793192 -931648 355041 81069
-639238 265325 279197 331273

output:

2798954762226.748853921890

result:

ok found '2798954762226.749023438', expected '2798954762226.749023438', error '0.000000000'

Test #24:

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

input:

37
-131846 614 862 168
-22220 13697 258 -10
26616 -348199 -210 1685
220 -329964 -150 1615
-13860 60289 170 -266
311355 32897 -2296 -138
366795 -11239 -2548 -475
555 281 504 -955
-2948 -280564 -6 1415
-27596 -307239 306 1525
-137036 8237 882 42
221496 -5164 -1834 -625
521411 -353499 -3164 1705
-76580...

output:

24803016000.000000000000

result:

ok found '24803016000.000000000', expected '24803016000.000000000', error '0.000000000'

Test #25:

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

input:

73
-108673 389998 924 -1380
-302273 81982 1804 276
306682 -227947 -2168 1350
-308909 -182187 1828 1030
27322 -840937 -616 4130
-278557 500974 1716 -1788
-97 386944 -324 -1368
-184673 -501697 1324 2810
6822 15454 -288 1068
48166 -114427 -832 470
-11009 -829377 28 4090
297882 9934 -2136 1188
-14657 23...

output:

50487256537.649006623775

result:

ok found '50487256537.649009705', expected '50487256537.649009705', error '0.000000000'

Test #26:

score: -100
Wrong Answer
time: 1ms
memory: 10056kb

input:

25
150 41240 110 -76
150 -71806 110 127
-135 100373 -117 -457
-135 -120701 -117 360
-135 -71304 -117 125
-135 -185507 -117 853
-135 -96206 -117 228
-135 -89846 -117 199
150 106114 110 -512
-135 -364728 -117 3338
-135 -240138 -117 1435
-135 -136915 -117 463
150 38262 110 -66
-135 -486593 -117 5988
15...

output:

3333063350.971023827558

result:

wrong answer 1st numbers differ - expected: '212632515.0000000', found: '3333063350.9710240', error = '14.6752289'