QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111628#5505. Great Chasexaphoenix#AC ✓1355ms10004kbC++141.5kb2023-06-07 19:44:192023-06-07 19:44:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-07 19:44:23]
  • 评测
  • 测评结果:AC
  • 用时:1355ms
  • 内存:10004kb
  • [2023-06-07 19:44:19]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 410000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int T, n;
double w, p[N], v[N];
int check(double x) {
	double mx = -INF, mn = INF;
	repn(i, 1, n) {
		if (p[i] < 0) mx = max(mx, p[i] + v[i] * x);
		else mn = min(mn, p[i] - v[i] * x);
	}
	return mx > mn;
}
int main() {
	IO;
	cin >> T;
	while (T--) {
		cin >> n >> w;
		repn(i, 1, n) cin >> p[i] >> v[i];
		double l = 0, r = 1e13;
		repn(rnd, 1, 100) {
			double mid = (l + r) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		cout << fixed << setprecision(15) << l * w << "\n";
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5808kb

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.250000000000000
1.230769230769231
3000000000000.000000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 795ms
memory: 5776kb

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.349090576171875
16414958969.727277755737305
5202715639.835183143615723
321977234.156325876712799
45384199210.221679687500000
183885744.769230753183365
1708925225.230472326278687
89786664971.557937622070312
13924365606.287387847900391
412975327.555555522441864
965508404.512101411819458
4...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 1353ms
memory: 5956kb

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.363636374473572
197971181.333333313465118
997533531.737629532814026
6439673170.665741920471191
993821598110.660888671875000
22727977326.402660369873047
34702455207.518501281738281
677770533.929817438125610
46631726883.969131469726562
5446481867.129032135009766
11336247450.272077560424805
4...

result:

ok 93 numbers

Test #4:

score: 0
Accepted
time: 1019ms
memory: 10004kb

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.811706542968750
511413015796.766479492187500
424240880533.634033203125000
518849481155.503906250000000
1882496988186.444091796875000

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 1355ms
memory: 8480kb

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.978591918945312
98630840901.507598876953125
29393530999.894321441650391
50801000770.955978393554688
39668001027.269325256347656
467846478226.411376953125000
30789914370.574310302734375
23151476830.905094146728516
51606123416.625823974609375
151713060001.662567138671875
100944679009.60928...

result:

ok 38 numbers