ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196117 | #2816. 小W的斜率 | tkswls | 100 | 1177ms | 16888kb | C++11 | 826b | 2023-10-19 09:22:35 | 2023-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'