UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196174#2816. 小W的斜率snow_trace1003844ms24644kbC++11946b2023-10-19 10:48:542023-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'