SP7778 ANARC09H - Land Division

遥远王国的国王去世了，这片土地需要在 $K$ 个儿子之间进行分配。这个国家的地图呈矩形形式，拥有 $N$ 座城市。为了实现划分，他们将在地图上画出 $K-1$ 条直线，所有的直线都是平行于垂直轴或者水平轴的。这些直线会将地图划分为恰好 $K$ 个矩形区域，所有矩形的高度（若为垂直分割）或宽度（若为水平分割）均相等。同时，任何一条分割线都不能穿过城市。接着，每位儿子将随机获得一个区域，区域中的城市归他所有。 自然，他们希望划分尽可能公平。理论上，每位儿子理想情况下应平均分得 $N/K$ 个城市，我们称其为基准值。但该值不总是整数，所以每位儿子都希望自己得到的城市数尽可能接近基准值。我们将每位儿子的不公平程度定义为他实际得到的城市数量与基准值的差的绝对值。最公平的分配是使所有儿子的平均不公平度最小的划分。 例如，假设有 3 个儿子和 6 个城市（基准值为 $6/3 = 2.0$）。原始地图如图 (a) 所示。图 (b) 显示了一种非最优的划分（虚线是分割线）。在此情况下，中间区域包含 3 座城市（不公平度为 $|3 - 2| = 1$），左边区域有 1 座城市（不公平度为 $|1 - 2| = 1$），而右边区域包含 2 座城市（完全公平，不公平度为 0），因此平均不公平度是 $2/3$。图 (c) 右边显示了最优的划分，因为三个区域各含相同数量的城市，平均不公平度为 0。因此，编写一个程序来确定如何实现最公平的土地划分。

你的程序需要处理一个或多个测试用例。每个测试用例共有 $N+1$ 行描述数据。第一行包含两个正整数：$N$ 和 $K$，接下来的 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，代表第 $i$ 座城市的坐标。

针对每个测试用例，输出一行： ``` k. A/B ``` 其中 $k$ 是测试用例编号（从 1 开始），$A/B$ 是最小可能的平均不公平度，且用最简分数表示。如果结果是整数，将 $B$ 设为 1。

- $1 \le N \le 10^5$ - $2 \le K \le 100$ - $0 \le X_i, Y_i \le 10^9$ **本翻译由 AI 自动生成**