首页 > 试题广场 >

小W的斜率

[编程题]小W的斜率

小W非常喜欢某个有理数P/Q，而且他非常喜欢用它来进行一些玄学操作。他在二维平面上撒下了n个点，这些点相互不同，但一番观察之后，他失望的发现并没有任何两个点连成的直线的斜率是P/Q。你能不能告诉他在这些斜率中最接近P/Q的是多少。

第一行包括三个正整数n,P,Q(5<=n<=10⁶,1<=P,Q<=10⁵)
接下来n行，每行两个正整数x,y表示点的坐标(0<=x,y<=10⁹)

一个有理数P’/Q’表示最接近P/Q的斜率

示例1

输入

6 15698 17433
112412868 636515040
122123982 526131695
58758943 343718480
447544052 640491230
162809501 315494932
870543506 895723090

193409386/235911335

保证答案唯一，且P’/Q’>0
斜率为无穷时可表示为1/0

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

计算几何数学

上传者：牛客301599号

难度：

0条回答 0收藏 18浏览

查看代码

小W的斜率

扫一扫，把题目装进口袋