4337. Effective Gradient

单点时限: 2.0 sec

内存限制: 256 MB

Little W likes rational number $\frac{P}{Q}$ very much. He has n points on the plane. You need to tell him the closest gradient to $\frac{P}{Q}$ of the lines passing through at least two points.

Suppose a line passes through two points $(x_0, y_0)$ and $(x_1, y_1)$. The gradient of it is exactly $g = \frac{y0 - y1}{x0 - x1}$. Closest gradient means $$\mathop{\arg\min} \limits_{g \in G} |g - \frac{P}{Q}|$$ as $G$ is the set of gradients of all availible lines.


The first lines contain three integers $n, P, Q$. $(5 \leq n \leq 10^6, 1 \leq P, Q \leq 10^5)$

In the following $n$ lines, each line contains two integers $x, y$ represent the coordinate of a point. $(1 \leq x,y \leq 10^9)$


You should output a rational number $P’$/$Q’$ represents the answer.

We ensure that the answer is unique and larger than 0.

You can use 1/0 to represent the gradient of infinity.


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

20 人解决,23 人已尝试。

22 份提交通过,共有 63 份提交。

4.4 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,9 月前.

最后提交: 1 年前.

来源: N/A