QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382202#8505. Almost Alignedkevinshan#WA 5672ms66568kbC++172.6kb2024-04-08 06:01:192024-04-08 06:01:20

Judging History

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

  • [2024-04-08 06:01:20]
  • 评测
  • 测评结果:WA
  • 用时:5672ms
  • 内存:66568kb
  • [2024-04-08 06:01:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long double
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n; cin>>n;
    ll x[n], y[n], vx[n], vy[n];
    for(int i=0; i<n; i++) cin>>x[i]>>y[i]>>vx[i]>>vy[i];

    ll ar = 5e18;
    vector<ll> deltas = {1e-8, 1e-9, 1e-10, 1e-11, 1e-12, 1e-13, 1e-14};
    for(auto delta:deltas){
        ll l = 0;
        ll r = 2e9;
        while(r - l >= delta) {
            ll m = (l+r)/2.0;
            ll mnx = x[0] + vx[0] * m;
            ll mxx = x[0] + vx[0] * m;
            ll mny = y[0] + vy[0] * m;
            ll mxy = y[0] + vy[0] * m;
            for(int i=1; i<n; i++){
                mnx = min(mnx, x[i] + vx[i] * m);
                mxx = max(mxx, x[i] + vx[i] * m);
                mny = min(mny, y[i] + vy[i] * m);
                mxy = max(mxy, y[i] + vy[i] * m);
            }

            ll md = m + delta;

            ll mnxd = x[0] + vx[0] * md;
            ll mxxd = x[0] + vx[0] * md;
            ll mnyd = y[0] + vy[0] * md;
            ll mxyd = y[0] + vy[0] * md;
            for(int i=1; i<n; i++){
                mnxd = min(mnxd, x[i] + vx[i] * md);
                mxxd = max(mxxd, x[i] + vx[i] * md);
                mnyd = min(mnyd, y[i] + vy[i] * md);
                mxyd = max(mxyd, y[i] + vy[i] * md);
            }

            if((mxx - mnx) * (mxy - mny) > (mxxd - mnxd) * (mxyd - mnyd) + delta){
                l = m;
            }
            else {
                r = m;
            }
            // cout<<l<<"|"<<r<<"\n";
            // cout<<(mxx - mnx) * (mxy - mny)<<"\n";
            ar = min(ar, (mxx - mnx) * (mxy - mny));
            ar = min(ar, (mxxd - mnxd) * (mxyd - mnyd));
        }
        for(int i=-10; i<=10; i++){
            ll m = i * delta/10 + l;
            if(m<0) continue;
            ll mnx = x[0] + vx[0] * m;
            ll mxx = x[0] + vx[0] * m;
            ll mny = y[0] + vy[0] * m;
            ll mxy = y[0] + vy[0] * m;
            for(int i=1; i<n; i++){
                mnx = min(mnx, x[i] + vx[i] * m);
                mxx = max(mxx, x[i] + vx[i] * m);
                mny = min(mny, y[i] + vy[i] * m);
                mxy = max(mxy, y[i] + vy[i] * m);
            }
            ar = min(ar, (mxx - mnx) * (mxy - mny));
        }
    }
    cout<<fixed<<setprecision(25)<<ar;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

22.2222222222222344657077686

result:

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

Test #2:

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

input:

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

output:

0.0000000000000026346112791

result:

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

Test #3:

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

input:

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

output:

4.0000000000000000000000000

result:

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

Test #4:

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

input:

1
0 0 0 0

output:

0.0000000000000000000000000

result:

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

Test #5:

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

input:

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

output:

3999984000031.9999520778656005859375000

result:

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

Test #6:

score: 0
Accepted
time: 5672ms
memory: 66268kb

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.0000000000000000000000000

result:

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

Test #7:

score: 0
Accepted
time: 5633ms
memory: 66568kb

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.0000000000000000000000000

result:

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

Test #8:

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

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.0000000000000000000000000

result:

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

Test #9:

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

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.0000000000000000000000000

result:

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

Test #10:

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

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.0368828078546812321292236

result:

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

Test #11:

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

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.4195011337933465256355703

result:

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

Test #12:

score: 0
Accepted
time: 527ms
memory: 10080kb

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.0000000000000000000000000

result:

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

Test #13:

score: 0
Accepted
time: 560ms
memory: 10084kb

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.5353860855102539062500000

result:

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

Test #14:

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

input:

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

output:

10.4843750000000162612978638

result:

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

Test #15:

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

input:

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

output:

20.0000000000000000000000000

result:

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

Test #16:

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

input:

1
2 -2 -1 -3

output:

0.0000000000000000000000000

result:

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

Test #17:

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

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.4444444444444465291965685

result:

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

Test #18:

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

input:

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

output:

6.0000000000000000000000000

result:

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

Test #19:

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

input:

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

output:

949518700936.0000000000000000000000000

result:

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

Test #20:

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

input:

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

output:

431585140930.0000000000000000000000000

result:

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

Test #21:

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

input:

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

output:

2493690369944.0792229175567626953125000

result:

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

Test #22:

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

input:

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

output:

577576180387.1008713841438293457031250

result:

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

Test #23:

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

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.7488868236541748046875000

result:

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

Test #24:

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

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.0000001341104507446289062

result:

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

Test #25:

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

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.6490068137645721435546875

result:

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

Test #26:

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

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:

212632515.0000000000000000000000000

result:

ok found '212632515.000000000', expected '212632515.000000000', error '0.000000000'

Test #27:

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

input:

41
-122 -202188 -87 806
-122 52097 -87 -91
-122 -110676 -87 239
-122 972577 -87 -39244
-122 75229 -87 -192
-122 56435 -87 -107
287 87094 60 -258
-122 -199083 -87 781
287 -184883 60 672
287 -275157 60 1505
-122 118150 -87 -478
-122 -278109 -87 1538
287 130564 60 -586
-122 143093 -87 -705
-122 68022 -...

output:

2712856246.4705614056438207626342773

result:

wrong answer 1st numbers differ - expected: '1191259126.0000000', found: '2712856246.4705615', error = '1.2773015'