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

    solution

    Đề bài: [Data Science] Gán cụm theo khoảng cách cosine

    Biến thể K-means hình cầu (spherical) dùng khoảng cách cosine. Cho nnn điểm và kkk tâm cụm cho trước, khoảng cách cosine giữa điểm xxx và tâm ccc:

    dcos⁡(x,c)=1−x⋅c∥x∥ ∥c∥d_{\cos}(x,c) = 1 - \frac{x\cdot c}{\lVert x\rVert\,\lVert c\rVert}dcos​(x,c)=1−∥x∥∥c∥x⋅c​

    Gán mỗi điểm về cụm có dcos⁡d_{\cos}dcos​ nhỏ nhất. Nếu hòa, chọn chỉ số cụm nhỏ hơn. In ra nhãn cụm của nnn điểm theo thứ tự.

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

      Dòng 1: nnn, ddd, kkk. Tiếp theo nnn dòng điểm. Tiếp theo kkk dòng tâm cụm.

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

      1≤n≤5001 \le n \le 5001≤n≤500, 2≤d≤102 \le d \le 102≤d≤10, 1≤k≤501 \le k \le 501≤k≤50. Bảo đảm mọi vector khác 0\mathbf{0}0.

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

      Một dòng gồm nnn số nguyên (nhãn cụm), cách nhau bởi dấu cách.

    Ví dụ:

    Đầu vào:

    2 2 2
2 1
-2 1
1 1
-1 1

    Đầu ra:

    0 1

    Giải thích:

    Điểm (2,1): cos với tâm0 (1,1) lớn hơn với tâm1 (-1,1) -> cụm 0. Điểm (-2,1): đối xứng -> cụm 1.

    Đang tải editor...