当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

基站聚类分析

模拟, 实现, 计算几何, K-Means, *2000

题目描述

Y 同学正在对一个区域的无线网络进行优化。该区域内有 $N$ 个基站，每个基站的位置由其二维坐标 $(x, y)$ 确定。为了提高信号覆盖质量，他需要通过一个精确的算法流程来确定一个新基站的最佳增设位置。

该算法流程严格分为以下三个步骤：

1. K-Means 聚类 你需要将 $N$ 个基站划分为 $K$ 个簇。

• 初始中心：选择输入数据中的前 $K$ 个基站作为 $K$ 个簇的初始聚类中心。
• 迭代过程：重复执行以下两个步骤： a. 分配：对于每个基站，计算其与所有 $K$ 个聚类中心的欧氏距离，并将其分配给距离最近的那个中心所代表的簇。 b. 更新：重新计算每个簇的聚类中心，新的中心为其簇内所有基站坐标的算术平均值。
• 终止条件：当以下任一条件满足时，迭代停止： a. 迭代次数达到 $100$ 次。 b. 所有 $K$ 个聚类中心在一次更新步骤中的移动距离（新旧中心之间的欧氏距离）均不超过 $10^{-6}$。

2. 轮廓系数计算 在聚类完成后，你需要为每个簇计算其轮廓系数。

• 对于簇内的任意一个基站 $p_i$，其轮廓系数 $s(p_i)$ 定义为：$$s(p_i) = \frac{b(p_i) - a(p_i)}{\max(a(p_i), b(p_i))} $$其中：
  • $a(p_i)$ 是 $p_i$ 与其所在簇内所有其他基站的平均欧氏距离。如果其所在簇只有一个基站，则 $a(p_i) = 0$。
  • $b(p_i)$ 是 $p_i$ 与其他某一个簇的所有基站的平均欧氏距离的最小值。
• 一个簇的轮廓系数，是该簇内所有基站的轮廓系数的平均值。

3. 确定新增位置

• 在所有 $K$ 个簇中，找出轮廓系数最低的那个簇。
• 新基站的增设位置，即为这个轮廓系数最低的簇的最终聚类中心。

请你实现上述完整的算法流程，并输出最终确定的新基站坐标。

输入格式

第一行包含两个由空格分隔的整数 $N$ 和 $K$，分别代表基站数量和目标聚类簇数。

接下来的 $N$ 行，每行包含两个整数 $x$ 和 $y$，表示一个基站的坐标。

输出格式

输出一行，包含两个浮点数，代表新增基站的 $x$ 坐标和 $y$ 坐标，以空格分隔。

结果需四舍五入保留两位小数。对于恰好为 .005 的情况，应向最近的偶数百分位舍入（例如 8.665 应舍入为 8.66，8.675 应舍入为 8.68）。

样例

样例输入 #1

6 2
0 0
1 1
2 2
10 10
11 11
5 5

样例输出 #1

8.67 8.67

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N \le 500$
• $1 \le K \le 120$
• $K \le N$
• $0 \le x \le 5000$
• $0 \le y \le 3000$
• 建议在计算中使用双精度浮点数以保证精度。