QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382190 | #8505. Almost Aligned | kevinshan# | WA | 1489ms | 66416kb | C++17 | 2.3kb | 2024-04-08 05:32:28 | 2024-04-08 05:32:29 |
Judging History
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 l = 0;
ll r = 2e9;
ll delta = 1e-13;
ll ar = 3e18;
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=-50; i<=50; i++){
ll m = i * delta + 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
22.2222222222234492353121205
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.0000000000000513651621237
result:
ok found '0.000000000', expected '0.000000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
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: 3880kb
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: 3936kb
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: 1489ms
memory: 66416kb
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: 1468ms
memory: 66316kb
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: 3868kb
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: 3784kb
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: 3892kb
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.0368828079415379761485383
result:
ok found '951042.036882808', expected '951042.036882808', error '0.000000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3832kb
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.4195011340719929648912512
result:
ok found '985195.419501134', expected '985195.419501134', error '0.000000000'
Test #12:
score: 0
Accepted
time: 144ms
memory: 9944kb
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: 165ms
memory: 10088kb
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.5409021377563476562500000
result:
ok found '3999945328884.541015625', expected '3999945328884.535156250', error '0.000000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 1 1 -2 -3 -2 1 4 -5 4 -1 0 -2 -3 -4 -1 5
output:
10.4843750000000374015055038
result:
ok found '10.484375000', expected '10.484375000', error '0.000000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3884kb
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: 3808kb
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: 3876kb
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.4444444444445298583734605
result:
ok found '69.444444444', expected '69.444444444', error '0.000000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3940kb
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: 3924kb
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: 3940kb
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: 3880kb
input:
4 554523 -843525 434069 -518131 910677 518840 -857480 -612229 231960 965891 333430 -440474 -687304 726302 164236 659483
output:
2493690369944.0878994464874267578125000
result:
ok found '2493690369944.087890625', expected '2493690369944.078125000', error '0.000000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 269831 -364179 -591251 516327 -578364 795567 -872538 -766732 -896806 -70577 -998004 159063 -962947 -103040 -47465 -189048
output:
577576180387.1120764017105102539062500
result:
ok found '577576180387.112060547', 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.7488868236541748046875000
result:
ok found '2798954762226.749023438', expected '2798954762226.749023438', error '0.000000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3936kb
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.0000034533441066741943359
result:
ok found '24803016000.000003815', expected '24803016000.000000000', error '0.000000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3840kb
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.6490182168781757354736328
result:
ok found '50487256537.649017334', expected '50487256537.649009705', error '0.000000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3808kb
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: 0ms
memory: 3840kb
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.4705619346350431442260742
result:
wrong answer 1st numbers differ - expected: '1191259126.0000000', found: '2712856246.4705620', error = '1.2773015'