QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270357#5505. Great Chasepooty#AC ✓544ms18316kbC++141.6kb2023-11-30 19:44:442023-11-30 19:44:45

Judging History

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

  • [2023-11-30 19:44:45]
  • 评测
  • 测评结果:AC
  • 用时:544ms
  • 内存:18316kb
  • [2023-11-30 19:44:44]
  • 提交

answer

#ifdef MY_LOCAL
#include "D://competitive_programming/debug/debug.h"
#define debug(x) cerr << "[" << #x<< "]:"<<x<<"\n"
#else
#define debug(x) 
#endif
#define REP(i, n) for(int i = 0; i < (n); i ++)
#define REPL(i,m, n) for(int i = (m); i < (n); i ++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define sz(X) ((int)X.size())
#define READ(arr) for(auto &a: arr){cin>>a;}
#define SUM(arr) accumulate((arr).begin(), (arr).end(), 0LL)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef tree<int,null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
const ll INF = 1e18;
#define double long double
void solve() {
	int n,v;cin>>n>>v;
	vii arr1;
	vii arr2;
	REP(i, n) {
		int p,vv;cin>>p>>vv;
		if (p < 0) {
			arr1.push_back({-p, vv});
		} else {
			arr2.push_back({p, vv});
		}
	}
	double EPS = 1e-9;
	double mn = 0;
	double mx = 1e13;
	while (mx - mn > EPS*mn) {
		double md = (mx + mn)/2;
		double b1 = -INF;
		double b2 = -INF;
		for (auto [x,y]: arr1) {
			b1 = max(b1, y*md - x);
		}
		for (auto [x,y]: arr2) {
			b2 = max(b2, y*md - x);
		}
		if (b1 + b2 >= 0) {
			mx = md;
		} else {
			mn = md;
		}
	}
	cout<<setprecision(13)<<mn*v<<"\n";
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	int tc;
	cin>>tc;
	REP(i, tc) {
		solve();
	}

}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3720kb

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.24999997676
1.230769230021
2999999999302

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 477ms
memory: 3628kb

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:

145405766227.3
16414958965.86
5202715637.36
321977233.9482
45384199201.35
183885744.7673
1708925224.32
89786664912.58
13924365599
412975327.3641
965508403.7355
4703493413.333
352961619.3039
5575125770.494
341191686.8917
985544508.0442
1370541507.122
143194575.0321
8728055563.922
28694043960.44
13681...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 544ms
memory: 4240kb

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.2737
197971181.235
997533531.6964
6439673168.998
993821598079.4
22727977324.25
34702455205.44
677770533.8543
46631726863.65
5446481865.254
11336247447.03
4409370839.609
15681606045.47
14986614228.18
1025909752.306
18994454575.72
105092139089.7
25758936823.53
252231500.6933
50720505852.35
4...

result:

ok 93 numbers

Test #4:

score: 0
Accepted
time: 528ms
memory: 18316kb

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:

519985220185.8
511413015696
424240880484.4
518849481058.7
1882496987695

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 524ms
memory: 8720kb

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:

89670748251.1
98630840899.84
29393530989.03
50801000767.15
39668001002.02
467846477970.2
30789914357.47
23151476823.11
51606123402.42
151713059913.7
100944678977.4
766785663898.4
39969642777.64
62341065910.64
323981604123
115228654959.8
52894567545.31
83882295605.06
20963769165.67
117523885615.8
373...

result:

ok 38 numbers