← 返回题目列表

Codeforces · 1361/D

D. 约翰尼和詹姆斯

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

约翰尼最喜欢的特工詹姆斯·邦德有一个新任务。有 $$$n$$$ 个敌人基地,每个基地都由其坐标描述,以便我们可以将它们视为笛卡尔平面中的点。

基座可以相互通信,发送信号,该信号是从所选点指向原点或相反方向的射线。中央基地是个例外,它位于原点,可以向任何方向发送信号。

当两个基地想要通信时,有两种可能的情况。如果它们与原点位于同一条线上,则其中一个可以直接向另一个发送信号。否则,信号从第一个基地发送到中央,然后中央再发送到第二个基地。我们将两个碱基之间的距离表示为它们之间发送的信号必须传播的总欧几里得距离。

Bond 可以损坏除了一些 $$$k$$$ 基地之外的所有基地,他可以任意选择这些基地。受损的基地无法发送或接收直接信号,但仍可以在两个工作基地之间传递信号。特别是,詹姆斯可以损坏中央基地,任意两个未损坏的基地之间仍然可以像以前一样发送信号,因此它们之间的距离保持不变。 007 通过精确损坏 $$$n - k$$$ 中的剩余碱基对可以达到的最大距离总和是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(2 \leq k \leq n \leq 5 \cdot 10^5)$$$ - 分别是碱基总数和必须保留的碱基数。

接下来的 $$$n$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ $$$(-10^9 \leq x, y \leq 10^9)$$$,第 $$$i$$$ 行包含第 $$$i$$$ 基数的坐标。您可以假设没有两个点重合,其中之一是 $$$(0, 0)$$$。

输出

您应该输出一个数字 - 给定碱基的所有 $$$k$$$ 对之间的最大可能距离总和。如果绝对或相对误差小于 $$$10^{-6}$$$,您的答案将被接受。

示例

输入 #1

6 2
0 0
1 1
2 2
3 3
0 1
0 2

输出 #1

6.24264069

输入 #2

6 5
0 0
1 1
2 2
3 3
0 1
0 2

输出 #2

32.62741700

输入 #3

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

输出 #3

237.00000000

输入#4

10 5
2 2
4 4
3 5
6 10
0 5
0 0
5 0
10 0
0 10
4 7

输出#4

181.52406315

注意

在第一个示例中,在最佳解决方案中,Bond 不会破坏索引为 $$$4$$$ 和 $$$6$$$ 的碱基(以橙色标记):

下图代表第二个示例的最佳解决方案。这些基地不会被摧毁:$$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$(以橙色标记)。

第三次测试的最佳解决方案在图中可见。只有基地 $$$3$$$、$$$4$$$、$$$5$$$ 被摧毁。同样,未摧毁的基地被标记为橙色。