QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77603 | #5505. Great Chase | zhangboju# | TL | 2ms | 5752kb | C++14 | 842b | 2023-02-15 10:02:00 | 2023-02-15 10:02:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
#define double long double
const int N=4e5+5;
const double eps=1e-8;
#define ll long long
int n;
ll p[N],v[N],k;
bool check(double x)
{
double maxx=-1e18,minx=1e18;
for(int i=1;i<=n;++i)
if(p[i]<0) maxx=max(maxx,p[i]+v[i]*x);
else minx=min(minx,p[i]-v[i]*x);
return minx<maxx;
}
int main()
{
int T;read(T);
while(T--)
{
read(n),read(k);
for(int i=1;i<=n;++i)
read(p[i]),read(v[i]);
double l=0,r=1e12;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.9Lf\n",l*k);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5752kb
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.249999969 1.230769230 3000000000000.000000000
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
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.343816385 16414958969.723367564 5202715639.832895368 321977234.151215863 45384199210.218583468 183885744.769183207 1708925225.223952702 89786664971.557044439 13924365606.286528771 412975327.554778009 965508404.508872971 4703493416.283940238 352961619.378364194 5575125771.793333292 34119...