ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196174 | #2816. 小W的斜率 | snow_trace | 100 | 3844ms | 24644kb | C++11 | 946b | 2023-10-19 10:48:54 | 2023-10-19 12:10:24 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,q;
struct node{
int x,y,val;
}a[1000005];
bool cmp(node a,node b){
return a.val<b.val;
}int gcd(int x,int y){
if(x == 0 or y == 0)return x|y;
return gcd(y,x%y);
}
signed main(){
cin>>n>>p>>q;
for(int i = 1;i<=n;i++){
cin>>a[i].x>>a[i].y;
a[i].val = q*a[i].y-p*a[i].x;
}sort(a+1,a+1+n,cmp);
long double ans = -2000000005,aim = 1.0*p/q;int p1 =0,p2 =0;
for(int i = 1;i<n;i++){
if(a[i].x == a[i+1].x)continue;
long double k = (1.0*a[i+1].y-a[i].y)/(1.0*a[i+1].x-a[i].x);
if(abs(aim-ans)>abs(aim-k)){
ans = k;p1 = i,p2 = i+1;
}
}//cout<<ans<<' '<<aim<<' ' <<p1<<' '<<p2<<endl;
int aa = a[p1].y-a[p2].y,bb = a[p1].x-a[p2].x;
//cout<< aa<<' '<<bb<<endl;
int g = gcd(aa,bb);aa/=g,bb/=g;
cout<<aa<< '/'<<bb<<endl;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1216kb
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: 1212kb
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: 1228kb
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: 1248kb
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: 1ms
memory: 1308kb
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: 7ms
memory: 1404kb
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: 10ms
memory: 1564kb
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: 22ms
memory: 1812kb
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: 35ms
memory: 2176kb
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: 66ms
memory: 2676kb
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: 76ms
memory: 3360kb
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: 98ms
memory: 4252kb
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: 153ms
memory: 5396kb
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: 195ms
memory: 6844kb
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: 271ms
memory: 8632kb
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: 329ms
memory: 10812kb
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: 432ms
memory: 13448kb
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: 564ms
memory: 16588kb
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: 707ms
memory: 20304kb
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: 878ms
memory: 24644kb
input:
1000000 16372 20687 675964 999595197 1586752 999768119 1108093 999310463 1178907 999351586 2213672 9...
output:
512327023/647355798
result:
ok single line: '512327023/647355798'