UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196117#2816. 小W的斜率tkswls1001177ms16888kbC++11826b2023-10-19 09:22:352023-10-19 12:08:54

answer

#include <bits/stdc++.h>
using namespace std;
long long n, p, q, maxx, maxy;
struct node {
	long long x, y;
} a[1000006];
long double cnt;
bool cmp(node w, node e) {
	return p * w.x - q * w.y < e.x * p - e.y * q;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + n + 1, cmp);
	cnt = 99;
	for (int i = 1; i < n; i++) {
		long long u = abs(a[i].x - a[i + 1].x), w = abs(a[i].y - a[i + 1].y);
		if (fabs(w * 1.0 / u - p * 1.0 / q) < cnt) {
			cnt = fabs(w * 1.0 / u - p * 1.0 / q);
			maxx = i;
		}
	}
	long long u = abs(a[maxx].x - a[maxx + 1].x), w = abs(a[maxx].y - a[maxx + 1].y);
	long long op = __gcd(u, w);
	u /= op;
	w /= op;
	cout << w << '/' << u << endl;
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1252kb

input:

6 15698 17433
112412868 636515040
122123982 526131695
58758943 343718480
447544052 640491230
1628095...

output:

193409386/235911335

result:

ok single line: '193409386/235911335'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1264kb

input:

100 1403 1232
47504824 948387241
174537398 922920553
79157413 814298143
259191697 978081463
10274687...

output:

21724482/19075997

result:

ok single line: '21724482/19075997'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1276kb

input:

506 6905 2178
690659 969665616
3362319 947217365
50157723 968609174
47504824 948387241
31875825 8517...

output:

504412361/159101222

result:

ok single line: '504412361/159101222'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1292kb

input:

1600 31286 6211
690659 969665616
3362319 947217365
13482600 950388805
846982 861638413
1681979 84036...

output:

458620051/91046767

result:

ok single line: '458620051/91046767'

Test #5:

score: 5
Accepted
time: 0ms
memory: 1332kb

input:

3906 12005 3512
690659 969665616
3362319 947217365
2807459 924561840
10895363 948530502
13482600 950...

output:

338759237/99102232

result:

ok single line: '338759237/99102232'

Test #6:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

8100 11476 26275
1658388 994707258
31864912 993056227
44106598 997083706
39096369 994791417
51022844...

output:

20312375/46506409

result:

ok single line: '20312375/46506409'

Test #7:

score: 5
Accepted
time: 3ms
memory: 1500kb

input:

15006 27729 22367
1658388 994707258
9875911 996322382
1309665 982779275
2687636 975314326
1856015 97...

output:

112484798/90733435

result:

ok single line: '112484798/90733435'

Test #8:

score: 5
Accepted
time: 7ms
memory: 1672kb

input:

25600 9422 6243
1658388 994707258
9875911 996322382
1309665 982779275
2687636 975314326
1856015 9730...

output:

96824923/64156017

result:

ok single line: '96824923/64156017'

Test #9:

score: 5
Accepted
time: 13ms
memory: 1908kb

input:

41006 25402 28091
1658388 994707258
4248957 992448369
9875911 996322382
5827708 990318192
17072427 9...

output:

185476832/205111003

result:

ok single line: '185476832/205111003'

Test #10:

score: 5
Accepted
time: 17ms
memory: 2248kb

input:

62500 515 246
1658388 994707258
4248957 992448369
1309665 982779275
3933523 987691494
5827708 990318...

output:

729579035/348497947

result:

ok single line: '729579035/348497947'

Test #11:

score: 5
Accepted
time: 22ms
memory: 2700kb

input:

91506 15707 20223
1658388 994707258
4248957 992448369
12016721 998408961
10750962 997261676
9875911 ...

output:

631008322/812432755

result:

ok single line: '631008322/812432755'

Test #12:

score: 5
Accepted
time: 31ms
memory: 3296kb

input:

129600 1613 3843
1658388 994707258
12016721 998408961
10750962 997261676
9346969 996611847
14699631 ...

output:

201805457/480804942

result:

ok single line: '201805457/480804942'

Test #13:

score: 5
Accepted
time: 46ms
memory: 4056kb

input:

178506 16097 30912
1380044 998422285
1383767 998108242
8763360 999475307
7533805 998693221
1658388 9...

output:

14839111/28496403

result:

ok single line: '14839111/28496403'

Test #14:

score: 5
Accepted
time: 67ms
memory: 5020kb

input:

240100 5171 21077
1178907 999351586
1380044 998422285
3946710 998761220
1383767 998108242
6787837 99...

output:

112599871/458957161

result:

ok single line: '112599871/458957161'

Test #15:

score: 5
Accepted
time: 79ms
memory: 6212kb

input:

316406 2931 28597
1178907 999351586
8763360 999475307
6787837 999166253
3946710 998761220
1380044 99...

output:

596514/5820031

result:

ok single line: '596514/5820031'

Test #16:

score: 5
Accepted
time: 105ms
memory: 7672kb

input:

409600 31409 27708
1178907 999351586
1586752 999768119
1380044 998422285
805206 997509924
1383767 99...

output:

331679983/292597312

result:

ok single line: '331679983/292597312'

Test #17:

score: 5
Accepted
time: 126ms
memory: 9428kb

input:

522006 2792 347
805206 997509924
1178907 999351586
114234 990289836
58010 988741337
1380044 99842228...

output:

139787587/17373314

result:

ok single line: '139787587/17373314'

Test #18:

score: 5
Accepted
time: 170ms
memory: 11524kb

input:

656100 22914 2555
805206 997509924
114234 990289836
1178907 999351586
58010 988741337
1380044 998422...

output:

147947779/16496752

result:

ok single line: '147947779/16496752'

Test #19:

score: 5
Accepted
time: 220ms
memory: 13992kb

input:

814506 737 6420
1586752 999768119
3145817 999938863
2213672 999793269
1178907 999351586
1108093 9993...

output:

13951531/121531654

result:

ok single line: '13951531/121531654'

Test #20:

score: 5
Accepted
time: 271ms
memory: 16888kb

input:

1000000 16372 20687
675964 999595197
1586752 999768119
1108093 999310463
1178907 999351586
2213672 9...

output:

512327023/647355798

result:

ok single line: '512327023/647355798'