OR93. 聚类

描述

铁柱在研究一个区域的小黄车使用分布。他得到了服务器上最近10000个用户的二维位置，现在他想把这些用户聚成K(K<10) 组，每组有一个中心C_i。他想评价聚类算法的好坏，把每个数据点到中心的l1距离作为总距离。即
D = sum_j || X_j - C( X_j ) ||_1
其中C(X_j)代表X_j所属的中心。现在他想找一个尽可能好的聚类算法，使得这个总距离尽可能小。要求你输出K个中心的位置（顺序不限）
比如如果有5个数据点
1 1
1 2
1 4
3 4
3 5
给定2个中心1 2， 3 4的话
总距离就是1+0+2+0+1 = 4

输入描述

本题总是会有10000个数据点
第一个输入为K，表示需要聚类的个数，
之后10000行，为每个点的x和y
例如：
2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2

输出描述

依次输出每个类中心

示例1

输入:

2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2

输出:

0.00000 0.00000
2.00000 2.00000

原站题解