Bài tập | NEU OJ

Bộ phận marketing phân cụm $n$ khách hàng (mỗi khách hàng là một vectơ đặc trưng $d$ chiều) bằng K-means. Cho trước $k$ tâm cụm $c_0, \dots, c_{k-1}$ , hãy thực hiện bước gán cụm: mỗi khách hàng $x_i$ được gán vào cụm có tâm gần nhất theo khoảng cách Euclid

$\|x - c\| = \sqrt{\sum_{j=1}^{d}(x_j - c_j)^2}$

Nếu có nhiều tâm cùng khoảng cách nhỏ nhất, chọn cụm có chỉ số nhỏ nhất.

Định dạng đầu vào:
Dòng đầu: ba số nguyên $n$ $d$ $k$ . $n$ dòng tiếp theo: mỗi dòng $d$ số thực (một khách hàng). $k$ dòng cuối: mỗi dòng $d$ số thực (một tâm cụm, theo thứ tự chỉ số 0..k−1).
Ràng buộc đầu vào:
1 ≤ n ≤ 1000; 1 ≤ d ≤ 10; 1 ≤ k ≤ 10; |giá trị| ≤ 1000.
Định dạng đầu ra:
Một dòng gồm $n$ số nguyên: chỉ số cụm (0-based) của từng khách hàng theo đúng thứ tự đầu vào, cách nhau dấu cách.

solution

Đề bài: [Data Science] Gán khách hàng vào cụm gần nhất