Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Data Science] Khách hàng xa tâm cụm nhất

    Sau khi phân cụm, đội chăm sóc khách hàng muốn tìm trong mỗi cụm khách hàng "bất thường" nhất — điểm xa tâm cụm nhất. Cho nnn điểm ddd chiều (chỉ số từ 0) và kkk tâm cụm:

    1. Gán mỗi điểm vào tâm gần nhất theo khoảng cách Euclid (hòa ⇒ chọn cụm chỉ số nhỏ nhất).
    2. Với từng cụm jjj từ 0 đến k−1k-1k−1: trong các điểm thuộc cụm jjj, tìm điểm có khoảng cách Euclid tới tâm cjc_jcj​ lớn nhất; nếu nhiều điểm cùng khoảng cách lớn nhất, chọn điểm có chỉ số nhỏ nhất.

    Với cụm có điểm, in chỉ số điểm đó và khoảng cách; cụm rỗng in -1.

    • Định dạng đầu vào:

      Dòng đầu: ba số nguyên nnn ddd kkk. nnn dòng tiếp theo: mỗi dòng ddd số thực (một điểm). kkk dòng cuối: mỗi dòng ddd số thực (một tâm cụm).

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 1000; 1 ≤ d ≤ 10; 1 ≤ k ≤ 10; |giá trị| ≤ 1000.

    • Định dạng đầu ra:

      kkk dòng. Dòng thứ jjj: nếu cụm jjj có điểm thì in chỉ số điểm xa nhất (số nguyên) và khoảng cách Euclid (làm tròn 2 chữ số thập phân {:.2f}) cách nhau dấu cách; nếu cụm rỗng in đúng -1.

    Ví dụ:

    Đầu vào:

    5 2 2
0 0
1 1
2 2
10 10
8 8
0 0
9 9

    Đầu ra:

    2 2.83
3 1.41

    Giải thích:

    Gán cụm: điểm 0,1,2 → cụm 0; điểm 3,4 → cụm 1. Cụm 0: xa nhất là điểm 2, khoảng cách √8 ≈ 2.83. Cụm 1: điểm 3 và 4 cùng cách tâm √2 ≈ 1.41, hòa ⇒ chọn chỉ số nhỏ là 3.

    Đang tải editor...