← 返回题目列表

AtCoder · abc263_h

Ex. 交叉路口 2

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

分数: 600 点

问题陈述

有 N 二维平面中的线。的 i第行是 A_i x + B_i y + C_i = 0。保证没有两条线平行。

在这个平面上,有 \frac{N(N-1)}{2} 两条线的交点,包括重复项。打印原点和原点之间的距离 K- 其中距离原点最近的点 \frac{N(N-1)}{2} 点。

约束

  • 2 \le N \le 5 \times 10^4
  • 1 \le K \le \frac{N(N-1)}{2}
  • -1000 \le |A_i|,|B_i|,|C_i| \le 1000(1 \le i \le N)
  • 没有两条线是平行的。
  • A_i \neq 0 or B_i \neq 0(1 \le i \le N).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

输出

打印代表答案的实数。

当法官输出的绝对或相对误差最多为 10^{-4}.


示例输入 1

3 2
1 1 1
2 1 -3
1 -1 2

示例输出 1

2.3570226040

让我们调用 i第 行 行 i.

  • 线的交点 1 和线 2 is (4,-5),其到原点的距离为 \sqrt{41} \simeq 6.4031242374.
  • 线的交点 1 和线 3 is (\frac{-3}{2},\frac{1}{2}),其到原点的距离为 \frac{\sqrt{10}}{2} \simeq 1.5811388300.
  • 线的交点 2 和线 3 is (\frac{1}{3},\frac{7}{3}),其到原点的距离为 \frac{5\sqrt{2}}{3} \simeq 2.3570226040.

因此,第二个最近的交点是 (\frac{1}{3},\frac{7}{3}),和 \frac{5\sqrt{2}}{3} 。


示例输入 2

6 7
5 1 9
4 4 -3
8 -1 2
0 1 -8
4 0 -4
2 -3 0

示例输出 2

4.0126752298