← 返回题目列表

Codeforces · 607/E

E. 交叉求和

中文机器翻译题面 查看原题

杰诺斯在笛卡尔平面上被赋予了 n 条不同的直线。令 $$\tau$$ 为这些线的交点列表。如果单个点是多对线的交点,则该点可能会在此列表中多次出现。列表的顺序并不重要。

给定一个查询点 (p, q),令 $$\mathcal{D}$$ 为 $$\tau$$ 中所有点到查询点的距离的对应列表。这里的距离是指欧氏距离。回顾一下,两点 (x1, y1) 和 (x2, y2) 之间的欧氏距离为 $$\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$$。

Genos 被赋予一个点 (p, q) 和一个正整数 m。他被要求找出 $$\mathcal{D}$$ 中 m 个最小元素的总和。 $$\mathcal{D}$$ 中的重复元素被视为单独的元素。杰诺斯被 Div1 E 问题吓坏了,所以他请求你的帮助。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 50 000) — 行数。

第二行包含三个整数 x、y 和 m (|x|, |y| ≤ 1 000 000, $${ 1 \leq m \leq \operatorname* { m i n } ( 3 \cdot 1 0 ^ { 7 }, | { \mathcal { D } } | ) }$$) — 查询点和查询点的编码坐标上述语句中的整数 m。查询点 (p, q) 的获取方式为 $$( \frac { x } { 1 0 0 0 }, \frac { y } { 1 0 0 0 } )$$。换句话说,将x和y除以1000即可得到实际的查询点。 $$|\mathcal{D}|$$ 表示列表 $$\mathcal{D}$$ 的长度,并且保证 $$|\mathcal{D}|>0$$。

接下来的 n 行中的每一行都包含两个整数 ai 和 bi (|ai|, |bi| ≤ 1 000 000) - 一行的参数,其形式为:$$y = \frac{a_i}{1000}x + \frac{b_i}{1000}$$。保证没有两条线是相同的,即如果 i ≠ j,则 (ai, bi) ≠ (aj, bj)。

输出

打印单个实数,$$\mathcal{D}$$ 的 m 个最小元素之和。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

为了澄清,我们假设您的答案是 a,陪审团的答案是 b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

4
1000 1000 3
1000 0
-1000 0
0 5000
0 -5000

输出 #1

14.282170363

输入 #2

2
-1000000 -1000000 1
1000000 -1000000
999999 1000000

输出 #2

2000001000.999999500

输入 #3

3
-1000 1000 3
1000 0
-1000 2000
2000 -1000

输出 #3

6.000000000

输入#4

5
-303667 189976 10
-638 116487
-581 44337
1231 -756844
1427 -44097
8271 -838417

输出#4

12953.274911829

注意

在第一个示例中,三个最近点的距离为 $$\sqrt{2}、4\sqrt{2}$$ 和 $$2\sqrt{13}$$。

在第二个示例中,两条线 y = 1000x - 1000 和 $$y = \frac{999999}{1000}x + 1000$$ 相交于 (2000000, 1999999000)。该点与 ( - 1000, - 1000) 的距离为 $$1000\sqrt{4000004004001}$$。

在第三个示例中,三条线均相交于点 (1, 1)。该交点在 $$\tau$$ 中出现了 3 次,因为它是三对线的交点。由于交点与查询点之间的距离为 2,因此答案是该点的三倍,即 6。