Trong hệ gợi ý sản phẩm, để tìm những khách hàng "giống nhất" với một khách hàng mới, ta dùng thuật toán k láng giềng gần nhất. Cho n điểm dữ liệu d chiều (chỉ số từ 0) và một điểm truy vấn q, hãy tìm k điểm gần q nhất theo khoảng cách Euclid.
Sắp xếp các điểm theo khoảng cách tăng dần; nếu hai điểm có cùng khoảng cách, điểm có chỉ số nhỏ hơn đứng trước. In chỉ số của k điểm đầu tiên theo thứ tự đó.
Dòng đầu: ba số nguyên n d k (k ≤ n). n dòng tiếp theo: mỗi dòng d số thực (một điểm dữ liệu). Dòng cuối: d số thực (điểm truy vấn q).
1 ≤ k ≤ n ≤ 1000; 1 ≤ d ≤ 10; |giá trị| ≤ 1000.
Một dòng gồm k số nguyên: chỉ số của k láng giềng gần nhất theo thứ tự khoảng cách tăng dần (hòa ⇒ chỉ số nhỏ trước), cách nhau dấu cách.
Ví dụ:
Đầu vào:
5 2 2
0 0
1 1
3 3
5 5
2 2
1 2
Đầu ra:
1 4
Giải thích:
Đang tải editor...