点集分组最小极差(Simple Grouping)

题目描述

本题对应 AtCoder Typical 90 第 045 题：Simple Grouping。

二维平面上有 $N$ 个点，第 $i$ 个点的坐标为 $(X_i, Y_i)$。

你需要将这 $N$ 个点划分为恰好 $K$ 个非空组，每个点恰好属于其中一个组。

定义一种划分方案的代价为：同一组内任意两点之间欧几里得距离平方的最大值。请你求出所有合法划分方案中代价的最小值。

输入格式

第一行包含两个正整数 $N, K$，分别表示点的数量与分组数量。

接下来 $N$ 行，每行包含两个整数 $X_i, Y_i$，表示第 $i$ 个点的坐标。

输出格式

输出一行一个整数，表示同组内两点距离平方最大值的最小可能值。

样例输入 #1

3 2
0 1
1 2
2 0

样例输出 #1

2

样例输入 #2

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

样例输出 #2

17

数据范围

对于 $100\%$ 的数据，$1 \le K \le N \le 15$，$0 \le X_i, Y_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接