解题思路

本题核心分为两部分：K-Means 聚类 + 路径距离计算。

首先使用 K-Means 算法对所有包裹进行聚类：

1. 初始化：

   • 按点到原点距离升序排序（相同则按输入顺序）

题目内容

某快递员负责一个片区的快递配送业务。假设他手头有 $N$ 个快递包裹需要派送，每个包裹对应一个具体的收货坐标$(x_i, y_i)$（单位：公里）。

为了提高效率，公司要求快递员先利用聚类算法将这 $N$ 个包裹自动划分为 $K$ 个簇（代表 $K$ 个社区），快递员只需要将快递送到社区中心（类的中心点)即可。快递员从起始位置出发，按照每个社区中心与起点之间的距离由近到远排序，依次送完所有社区的快递，最后返回起始位置。已知快递员的平均行驶速度为 speed km/h。

快递员初始坐标为 $(0, 0)$。请编写程序，计算完成所有配送并返回起点所需的总时间（单位：秒，向下取整）。

K-Means 聚类计算步骤

• 种子点初始化

​ 将所有点按到起点的距离从小到大排序，如果距离相同的点，按照输入坐标点的先后顺 序从小到大排序

​ 选择排序后的前 $K$个点作为初始聚类中心。

• 迭代优化

​ 将每个点 $p_i$分配到距离最近的聚类中心 $c_k$

​ $label_i = \arg\min_k dist(p_i, c_k)$

​ 重新计算每个聚类的中心点（$n_k$ 表示分配到第$k$ 个聚类中心的坐标点个数），移动聚类中心

​ $c_k = \left( \frac{1}{n_k} \sum_{i}^{n_k} x_i,\ \frac{1}{n_k} \sum_{i}^{n_k} y_i \right)$

• 收敛判断

​ 如果所有聚类中心的移动距离之和小于 1e-4，则停止迭代 ​ 如果达到了预设的最大迭代轮次，也停止迭代 ​ 否则返回第二步继续进行迭代优化

输入描述

第一行输入 3 个由空格分隔的整数，分别为 $K$（社区个数）、$N$（快递包裹总数）、speed（快递员平均行驶速度，单位 km/h）。

接下来的 $N$ 行分别表示每个包裹的 $x$和$y$ 坐标（单位：公里），用空格分割。

输出描述

输出快递员送完所有快递所需的时间，保留整数，向下取整，单位 s。

样例1

输入

3 10 30
1.2 1.5
1.8 1.2
5.0 5.2
5.5 4.8
4.9 5.5
-2.0 3.0
-2.5 3.5
-1.8 2.8
1.5 1.8
5.2 5.0

输出

2502

说明

第一行输入，3 个社区，10 个快递包，快递员配送速度 30 km/h 第二行及以后表示，10 个快递包的具体坐标位置，x，y 坐标值，共有 10 行，代表 10 个包裹 聚类后的 3 个聚类中心按照距离起点的位置远近排序分别为：（1.5, 1.5），（-2.1, 3.1），（5.15, 5.125） 可算出快递员配送总时间约为 2502 秒

样例2

输入

5 3 10
1.00 1.00
2.00 2.00
3.00 3.00

输出

3054

说明

第一行输入，5 个社区，3 个包裹，快递员配送速度 10 km/h 第二行及以后表示，3 个快递包的具体坐标位置，x，y 坐标值，共有 3 行，代表 3 个包裹

​ 由于 5 > 3，3 个包裹本身分别构成了 3 个聚类中心，按照距离起点位置的排序配送的路径为：

1. (0, 0) --> (1, 1) --> (2, 2) --> (3, 3) --> (0, 0)

总距离为：$6\sqrt{2}$ km,配送速度为 10 km/h，总耗时为

$3600 \times 6\sqrt{2} \div 10 \approx 3054.70$秒，向下取整后为 3054 秒，故输出 3054。

提示

解题约束及提示

1.1 使用欧式距离：$dist = \sqrt{(x1 - x2)^2 + (y1 - y2)^2}$

1.2 种子点的选择：对距离信息 dist 进行升序排序，选择前 K 个点进行初始化

1.3 k-Means 终止条件，设定常数

const int max_iters = 50;

const double tol = 1e-4;

1.4 用例数值范围

$1 <= K <= 10$

$1 <= N <= 100$

$1 <= speed <= 100$