QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382204#8505. Almost Alignedkevinshan#WA 5035ms66260kbC++172.6kb2024-04-08 06:02:552024-04-08 06:02:55

Judging History

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

  • [2024-04-08 06:02:55]
  • 评测
  • 测评结果:WA
  • 用时:5035ms
  • 内存:66260kb
  • [2024-04-08 06:02:55]
  • 提交

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-7, 1e-8, 1e-9, 1e-10, 1e-11, 1e-12};
    for(auto delta:deltas){
        ll l = 0;
        ll r = 2e11;
        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: 1ms
memory: 3692kb

input:

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

output:

22.2222222222247244183962467

result:

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

Test #2:

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

input:

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

output:

0.0000000000002452933689501

result:

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

Test #3:

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

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: 3732kb

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: 3904kb

input:

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

output:

3999984000031.9999547004699707031250000

result:

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

Test #6:

score: 0
Accepted
time: 5035ms
memory: 66260kb

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: 4993ms
memory: 66240kb

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: 3756kb

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: 0ms
memory: 3744kb

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: 0ms
memory: 4036kb

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

result:

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

Test #11:

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

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

result:

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

Test #12:

score: 0
Accepted
time: 477ms
memory: 10144kb

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: 490ms
memory: 10012kb

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

result:

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

Test #14:

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

input:

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

output:

10.4843750000013591688538539

result:

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

Test #15:

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

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: 1ms
memory: 3828kb

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: 0ms
memory: 3736kb

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

result:

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

Test #18:

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

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: 3880kb

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: 3936kb

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: 3968kb

input:

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

output:

2493690369944.1389346122741699218750000

result:

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

Test #22:

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

input:

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

output:

577576180387.1847395300865173339843750

result:

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

Test #23:

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

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

result:

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

Test #24:

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

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

result:

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

Test #25:

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

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

result:

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

Test #26:

score: -100
Wrong Answer
time: 0ms
memory: 3888kb

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

result:

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