20 人解决,23 人已尝试。
22 份提交通过,共有 63 份提交。
4.4 EMB 奖励。
单点时限: 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
193409386/235911335
20 人解决,23 人已尝试。
22 份提交通过,共有 63 份提交。
4.4 EMB 奖励。
创建: 3 年,1 月前.
修改: 3 年,1 月前.
最后提交: 1 年,5 月前.
来源: N/A