首页 > 试题广场 >

聚类

[编程题]聚类
  • 热度指数：578 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
铁柱在研究一个区域的小黄车使用分布。他得到了服务器上最近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
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 安卓工程师 商汤科技 模拟 穷举 算法工程师 高级算法 2018 Java工程师
上传者：小小
难度：
5条回答 4085浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号