QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607046 | #5505. Great Chase | QHhee004# | AC ✓ | 1040ms | 10136kb | C++17 | 899b | 2024-10-03 13:45:53 | 2024-10-03 13:45:54 |
Judging History
answer
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
typedef long double ldb;
const int N=400005;
const ldb eps=1e-15l;
int n,v;
LL standar;
struct People {
LL s;
int v;
} A[N];
bool check(ldb t) {
ldb lowS=-1e13,uprS=1e13;
for(int i=1; i<=n; i++) {
if(A[i].s<0) {
if(A[i].v*t+A[i].s>lowS) lowS=A[i].v*t+A[i].s;
} else {
if(A[i].s-A[i].v*t<uprS) uprS=A[i].s-A[i].v*t;
}
}
return uprS<=lowS;
}
void solve() {
// printf("%.8Lf\n",1e16l+5e-8l);
scanf("%d%d",&n,&v);
for(int i=1; i<=n; i++) {
scanf("%lld%d",&A[i].s,&A[i].v);
}
ldb L=0,R=1e14,ans=0;
while(R-L>eps) {
ldb mid=(L+R)/2;
if(check(mid)) {
ans=mid;
if(R-mid<eps)break;
R=mid;
}
else {
if(mid-L<eps)break;
L=mid;
}
}
printf("%.8Lf\n",ans*v);
}
int main() {
int T;scanf("%d",&T);
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
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.25000000 1.23076923 3000000000000.00000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 551ms
memory: 3876kb
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.34911004 16414958969.72728119 5202715639.83518390 321977234.15632587 45384199210.22168397 183885744.76923077 1708925225.23047236 89786664971.55794264 13924365606.28738880 412975327.55555556 965508404.51210149 4703493416.28837652 352961619.38104382 5575125771.79879716 341191687.00011621 ...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 1040ms
memory: 4332kb
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.36363636 197971181.33333333 997533531.73762959 6439673170.66574179 993821598110.66107786 22727977326.40266099 34702455207.51850403 677770533.92981750 46631726883.96913324 5446481867.12903226 11336247450.27207859 4409370840.43913163 15681606050.57628686 14986614231.54685930 1025909753.14298...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 748ms
memory: 10136kb
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.81177092 511413015796.76647538 424240880533.63402033 518849481155.50391880 1882496988186.44400001
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 920ms
memory: 8500kb
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.97860802 98630840901.50760696 29393530999.89432779 50801000770.95598542 39668001027.26933134 467846478226.41137084 30789914370.57431161 23151476830.90509843 51606123416.62582759 151713060001.66258892 100944679009.60928628 766785664078.35898173 39969642788.06186739 62341065938.36004273 32...
result:
ok 38 numbers