QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363819#8505. Almost Aligneducup-team2000#WA 3296ms34528kbC++201.6kb2024-03-24 03:46:302024-03-24 03:46:31

Judging History

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

  • [2024-03-24 03:46:31]
  • 评测
  • 测评结果:WA
  • 用时:3296ms
  • 内存:34528kb
  • [2024-03-24 03:46:30]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define f first
#define s second
#define lep(i,a,b) for (int i=(a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)

typedef long double D;

const D inf = 1e10;
const D large_val = 1e50;

#define EPS 1e-12

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    D l = 0;
    D r = inf;
    vector<int> x(n+1),y(n+1),vx(n+1),vy(n+1);
    lep(i,1,n) {
        cin >> x[i] >> y[i] >> vx[i] >> vy[i];
    }
    auto F = [&](D t) -> D {
        D minx = large_val;
        D maxx = -large_val;
        D miny = large_val;
        D maxy = -large_val;
        lep(i,1,n) {
            D xval = D(x[i]) + D(t) * D(vx[i]);
            D yval = D(y[i]) + D(t) * D(vy[i]);
            minx = min(minx, xval);
            miny = min(miny, yval);
            maxx = max(maxx, xval);
            maxy = max(maxy, yval);
        }
        D ans = (maxy - miny) * (maxx - minx);
        // cout << "t: " << t << ", ans: " << ans << "\n";
        return ans;
    };
    // cout << fixed << setprecision(10);
    // while (r - l > EPS) {
    //     cout << "l: " << l << ", r: " << r << "\n";
    lep(it,1,400) {
        D dif = r - l;
        D m1 = l + dif * D(.49999);
        D m2 = l + dif * D(.50001);
        D ans1 = F(m1);
        D ans2 = F(m2);
        if (ans1 > ans2) l = m1;
        else r = m2;
    }
    cout << fixed << setprecision(15) << F((l + r) / 2) << "\n";

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

22.222222222222223

result:

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

Test #2:

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

input:

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

output:

0.000000000000000

result:

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

Test #3:

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

input:

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

output:

4.000000000000000

result:

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

Test #4:

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

input:

1
0 0 0 0

output:

0.000000000000000

result:

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

Test #5:

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

input:

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

output:

3999984000032.012466669082642

result:

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

Test #6:

score: 0
Accepted
time: 3296ms
memory: 34528kb

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

result:

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

Test #7:

score: 0
Accepted
time: 3262ms
memory: 34440kb

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

result:

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

Test #8:

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

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

result:

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

Test #9:

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

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

result:

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

Test #10:

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

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

result:

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

Test #11:

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

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

result:

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

Test #12:

score: 0
Accepted
time: 327ms
memory: 6212kb

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

result:

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

Test #13:

score: 0
Accepted
time: 330ms
memory: 6256kb

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

result:

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

Test #14:

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

input:

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

output:

10.484375000000064

result:

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

Test #15:

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

input:

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

output:

20.000000000000000

result:

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

Test #16:

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

input:

1
2 -2 -1 -3

output:

0.000000000000000

result:

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

Test #17:

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

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

result:

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

Test #18:

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

input:

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

output:

6.000000000000000

result:

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

Test #19:

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

input:

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

output:

949518700936.000000000000000

result:

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

Test #20:

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

input:

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

output:

431585140930.000315636396408

result:

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

Test #21:

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

input:

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

output:

2493690369944.080637931823730

result:

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

Test #22:

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

input:

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

output:

577576180387.101424157619476

result:

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

Test #23:

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

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

result:

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

Test #24:

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

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

result:

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

Test #25:

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

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

result:

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

Test #26:

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

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

result:

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

Test #27:

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

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:

1191259126.000000000000000

result:

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

Test #28:

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

input:

21
119 -197341 278 623
119 237192 278 -1735
-170 115213 -179 -407
119 -333873 278 1788
-170 -123517 -179 243
119 106232 278 -346
-170 76440 -179 -179
119 -243252 278 947
-170 77161 -179 -182
-170 -116197 -179 215
-170 -418509 -179 2815
119 -156876 278 393
-170 142274 -179 -622
119 99148 278 -301
119...

output:

10721817671.539858149364591

result:

wrong answer 1st numbers differ - expected: '194540639.0000000', found: '10721817671.5398579', error = '54.1135111'