QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77603#5505. Great Chasezhangboju#TL 2ms5752kbC++14842b2023-02-15 10:02:002023-02-15 10:02:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-15 10:02:02]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5752kb
  • [2023-02-15 10:02:00]
  • 提交

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

result: