配点: 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