鐵柱在研究一個(gè)區(qū)域的小黃車使用分布署穗。他得到了服務(wù)器上最近10000個(gè)用戶的二維位置,現(xiàn)在他想把這些用戶聚成K(K<10) 組嵌洼,每組有一個(gè)中心C_i案疲。他想評(píng)價(jià)聚類算法的好壞,把每個(gè)數(shù)據(jù)點(diǎn)到中心的l1距離作為總距離麻养。即
D = sum_j || X_j - C( X_j ) ||_1
其中C(X_j)代表X_j所屬的中心『址龋現(xiàn)在他想找一個(gè)盡可能好的聚類算法,使得這個(gè)總距離盡可能小鳖昌。要求你輸出K個(gè)中心的位置(順序不限)
比如如果有5個(gè)數(shù)據(jù)點(diǎn)
1 1
1 2
1 4
3 4
3 5
給定2個(gè)中心1 2备畦, 3 4的話
總距離就是1+0+2+0+1 = 4
輸入描述:
本題總是會(huì)有10000個(gè)數(shù)據(jù)點(diǎn)
第一個(gè)輸入為K,表示需要聚類的個(gè)數(shù)许昨,
之后10000行懂盐,為每個(gè)點(diǎn)的x和y
例如:
2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2
輸出描述:
依次輸出每個(gè)類中心
輸入例子1:
2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2
輸出例子1:
0.00000 0.00000
2.00000 2.00000