题目背景
岁月荏苒,光阴如梭。谁不是此刻方知一切往事不过惊鸿照影,或本就是匆匆过客,或终将散入云烟,不曾改变。
没错,时间的使命是涤荡悲哀,而不是留住美好。
历史的年轮,命运的轨迹……不,$\text{goodier}$ 不忍心如此,更绝不甘心如此——毕竟,我们能做的,还有珍惜。
那么,就请你帮助他一同找寻回忆中最美好的印记吧!
题目描述
$\text{goodier}$ 一共有 $n$ 个美好的回忆,每一个回忆都可以看作是一条美丽的直线 $y = a_i x + b_i$,而这些回忆互相交错编制便形成了无数的印记,每一个印记都可以看作是两条回忆的交点。$\text{goodier}$ 自身则可以看作是茫茫回忆中的一个点 $(x, y)$。
现在 $\text{goodier}$ 要在这无数的印记中找到最美好的一个,因为他觉得最美好的印记是离他有一段距离的,所以他认为距离他第 $k$ 近的印记才是最美好的,现在他想知道最美好的印记是由哪两个回忆编织而成的。
具体地来说,给定 $n$ 条直线(保证不存在两条相同的直线)和一个点 $P(x, y)$,找到距离点 $P$ 第 $k$ 近的交点,并求出该交点是由哪两条直线相交而成的。
注意,在本题中两个印记的位置有可能重合,例如当有四条直线同时经过点 $(1,2)$ 时,我们认为该处有六个交点(四条直线两两都构成交点)。
从 memory.in 中读入数据。
第一行五个整数 $n, k, x, y, id$,分别表示一共有 $n$ 个回忆;他认为的最美好的印记是距他第 $k$ 远的印记;$\text{goodier}$ 在 $(x, y)$ 位置;该数据点所处子任务编号为 $id$(在样例中 $id=0$)。
接下来 $n$ 行,每行两个整数 $a_i, b_i$,表示第 $i$ 个回忆可以看作是直线 $y = a_i x + b_i$。
将答案输出到 memory.out 中。
一行两个整数 $i, j$,表示第 $i$ 个回忆和第 $j$ 个回忆编织而成的印记是距离 $\text{goodier}$ 第 $k$ 近的印记。
如果有多组解,任意输出一种即可。
如果你输出的两个回忆编织而成的印记到 $\text{goodier}$ 的距离和真正的距 $\text{goodier}$ 第 $k$ 近的印记到 $\text{goodier}$ 的距离误差(绝对误差或相对误差)不超过 $10^{-4}$,则也认为你的答案是正确的。
数据范围
对于 $100\%$ 的数据,$1\leq n \leq 3\times 10^4, 0 \leq |x|, |y|, |a_i|, |b_i| \leq 1.5\times 10^4$,且保证有交点, $k$ 不超过总交点数。
注意精度哦。
