← 返回题目列表

AtCoder · typical90_as

045. 简单分组(★6)

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

配点: 6 点

問題文

在欧几里得平面上,N 点 (X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N) 有。 考虑将它们分成满足以下条件的 K 个组。

  • 不得有点属于多个组。
  • 不得有点不属于任何组。
  • 不得有组没有任何点。

此时,在同一组内的 2 点间距离的最大值请最小化。 但是,对于裁判来说,在此时同一组内的 2 点间距离的最大值的 2 乘法 计算除以 请输出。

此时的最大值 2 乘方的值可以被证明一定是整数。

制約

  • 2\leq K< N\leq 15
  • 0\leq X_i,Y_i\leq 10^9
  • (X_i,Y_i)\neq (X_j,Y_j) (i\neq j)
  • 所有输入均为整数

入力

输入以以下格式给出。

N K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

对于所有可能的分组方法,同一组内的 2 当计算点之间距离的最大值时,它的最小值 可以得到第 2 乘法 计算除以 用整数表示 1 行输出。


入力例 1

3 2
0 1
1 2
2 0

出力例 1

2

\{(0,1),(1,2)\}, \{(2,0)\} 分开后,同一组内的 2 点之间的距离最大值为 \sqrt 2 因为这是最小的,所以将其 2 次方后 2 。


入力例 2

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

出力例 2

4

\{(0,0),(0,2)\}, \{(1,1),(3,1)\}, \{(2,3)\} 分开,距离的最大值有 2 的两组,其最大值为 2 。

\{(0,0)\}, \{(0,2),(1,1)\}, \{(2,3),(3,1)\} 也可以分成其他方式,但在这种情况下,同一组内的 2 点之间距离为 \sqrt2 和 按字典顺序比较 \sqrt5 。 对于


入力例 3

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

出力例 3

20

入力例 4

3 2
0 0
500000000 500000000
1000000000 1000000000

出力例 4

500000000000000000