QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105735 | #5505. Great Chase | LeticiaFCS | AC ✓ | 1053ms | 19260kb | C++20 | 1.2kb | 2023-05-15 09:46:28 | 2023-05-15 09:46:31 |
Judging History
answer
#include"bits/stdc++.h"
using lint = int64_t;
constexpr int MOD = int(1e9) + 7;
constexpr int INF = 0x63636363;
constexpr int NINF = 0xcfcfcfcf;
constexpr lint LINF = 0x6363636363636363;
using namespace std;
using ld = double;
void solve(){
int n; cin>>n;
ld ini_v;
cin>>ini_v;
vector<pair<ld, ld>> left, right;
for(int i =0; i<n; i++){
ld p, v;
cin>>p>>v;
if(p < 0) left.emplace_back(p, v);
else right.emplace_back(p, v);
}
ld lo = 0, hi = 3000000000001;
for(int it = 300; it--; ){
ld mid = (lo + hi) / 2;
ld min_right = 3000000000001;
ld max_left = -3000000000001;
for(auto [p, v]: left){
ld cur_p = p + v * mid;
max_left = max(max_left, cur_p);
}
for(auto [p, v]: right){
ld cur_p = p - v * mid;
min_right = min(min_right, cur_p);
}
if(min_right < max_left) hi = mid;
else lo = mid;
}
cout<<fixed<<setprecision(20)<<hi * ini_v<<"\n";
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int t; cin>>t;
while(t--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3748kb
input:
3 4 9 10 2 -7 2 -6 1 7 1 2 8 -1 7 1 6 2 3 -1000000000000 1 1000000000000 1
output:
38.25000000000000710543 1.23076923076923083755 3000000000000.00048828125000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 932ms
memory: 3528kb
input:
10000 200 997007 405524182320 754760 686939601648 419804 687047488212 715566 1446157132 4594 -670522037 4673 763634629282 253755 424307411732 275041 1582708381 8473 -667425982 4622 -522841486 1427 702430907988 460271 1405423646 1060 1497754648 6227 883363410675 723547 56899800372 46435 -810216390 64...
output:
145405766328.34912109375000000000 16414958969.72728157043457031250 5202715639.83518409729003906250 321977234.15632593631744384766 45384199210.22168731689453125000 183885744.76923078298568725586 1708925225.23047256469726562500 89786664971.55795288085937500000 13924365606.28738975524902343750 41297532...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 863ms
memory: 4292kb
input:
93 15435 968117 4196666 184 -5069875 255 -9782648 980 -1978138 176 9333323 764 -4323540 12 -8442049 319 -5371878 137 2881306 10 -4050629 133 -4659099 59 -5189169 320 -2256647 99 -3686648 37 1059255 33 -223142 20 8040933 408 8407764 705 694547 38 -7913614 746 -3573355 132 5919585 189 -3756662 94 -795...
output:
189662921.36363637447357177734 197971181.33333334326744079590 997533531.73762977123260498047 6439673170.66574192047119140625 993821598110.66101074218750000000 22727977326.40266418457031250000 34702455207.51850891113281250000 677770533.92981755733489990234 46631726883.96913909912109375000 5446481867....
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 1053ms
memory: 19260kb
input:
5 400000 999972 172811492468 106699 171900177092 102097 194121748377 184014 190302947556 172722 183121572232 149212 196566712700 190884 171376795991 99358 522927044000 159597 -129031052077 34395 189422320931 170012 -275879974024 638546 408864707565 98475 -106703244806 368801 192128798630 178213 2915...
output:
519985220219.81176757812500000000 511413015796.76654052734375000000 424240880533.63409423828125000000 518849481155.50396728515625000000 1882496988186.44409179687500000000
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 1053ms
memory: 8468kb
input:
38 16668 999947 -3844782803 511 -210897941456 464872 618726004990 714384 -954596898686 225256 96675744 1148 -1515974078 11375 -206213840984 706184 306078847 3947 -474818331950 391451 -616022698917 561244 123378707 1540 -640636592655 406006 459201391325 908506 -733249583 5719 496163273 6238 619876911...
output:
89670748252.97860717773437500000 98630840901.50761413574218750000 29393530999.89432525634765625000 50801000770.95598602294921875000 39668001027.26933288574218750000 467846478226.41143798828125000000 30789914370.57431411743164062500 23151476830.90509796142578125000 51606123416.62583160400390625000 15...
result:
ok 38 numbers