CF1361D Johnny and James

詹姆斯·邦德（James Bond），Johnny 最喜欢的特工，接到了一个新任务。有 $n$ 个敌方基地，每个基地由其坐标描述，因此我们可以将它们视为平面直角坐标系上的点。 这些基地之间可以通过发送信号进行通信，信号是从选定的点指向原点或相反方向的射线。唯一的例外是位于原点的中央基地，它可以向任意方向发送信号。 当两个基地需要通信时，有两种情况。如果它们与原点共线，则其中一个可以直接向另一个发送信号。否则，信号会从第一个基地传送到中央基地，再由中央基地传送到第二个基地。我们将两个基地之间的距离定义为信号在它们之间传递所需经过的欧几里得距离总和。 邦德可以破坏除 $k$ 个基地外的所有基地，这 $k$ 个基地可以任意选择。被破坏的基地无法直接发送或接收信号，但仍然可以作为中继站在两个完好的基地之间传递信号。特别地，邦德也可以破坏中央基地，但信号仍然可以像之前一样在任意两个未被破坏的基地之间传递，因此它们之间的距离保持不变。请问，007 通过恰好破坏 $n-k$ 个基地后，剩下的 $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)$。

输出一个数，表示通过破坏恰好 $n-k$ 个基地后，剩余 $k$ 个基地之间所有两两配对的距离之和的最大值。你的答案如果与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

在第一个样例中，最优方案是邦德不破坏编号为 $4$ 和 $6$ 的基地（橙色标记）：  下图展示了第二个样例的最优方案。未被破坏的基地为 $2$、$3$、$4$、$5$、$6$（橙色标记）。  第三个样例的最优方案如图所示。只有基地 $3$、$4$、$5$ 被破坏，未被破坏的基地同样以橙色标记。  由 ChatGPT 4.1 翻译