from math import sqrt
from collections import Counter

points = [
    ("P1", (1, 1), "A"),
    ("P2", (3, 3), "B"),
    ("P3", (1, 3), "A"),
    ("P4", (3, 1), "B"),
]
q = (1.5, 1.5)
rows = []
for row_id, point, label in points:
    d2 = (point[0] - q[0]) ** 2 + (point[1] - q[1]) ** 2
    rows.append((d2, row_id, label))
rows.sort()
for d2, row_id, label in rows:
    print(row_id, label, d2, round(sqrt(d2), 4))
neighbors = rows[:3]
votes = Counter(label for d2, row_id, label in neighbors)
prediction = sorted(votes.items(), key=lambda item: (-item[1], item[0]))[0][0]
print("k=3 vote:", dict(sorted(votes.items())), "prediction=", prediction)