Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек), лежащих внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит ровно одному кластеру. Центроид кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Расстояние между звёздами вычисляется по формуле Евклида: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)
Вам дан список координат звёзд и количество кластеров k. Известно, что все кластеры имеют размер \(H \times W\) и чётко разделены (расстояние между кластерами значительно больше их размера).
Необходимо:
1. Разделить звёзды на k кластеров
2. Найти центроид каждого кластера
3. Вычислить \(P_x\) — среднее арифметическое x-координат всех центроидов
4. Вычислить \(P_y\) — среднее арифметическое y-координат всех центроидов
5. Вывести результат в заданном формате
Формат входных данных
- Первая строка содержит два целых числа n и k (\(1 \le n \le 1000\), \(1 \le k \le 10\)) — количество звёзд и количество кластеров.
- Вторая строка содержит два вещественных числа H и W — размеры каждого кластера.
- Следующие n строк содержат по два вещественных числа \(x_i\)и \(y_i\) (\(-10^6 \le x_i, y_i \le 10^6\)) — координаты звёзд.
Формат выходных данных
Выведите два целых числа через пробел:
- Целую часть от \(|P_x \times 10000|\)
- Целую часть от \(|P_y \times 10000|\)
где |x| обозначает абсолютное значение числа x.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
3 3
0 0
1 0
0 1
10 10
11 10
10 11
|
50000 50000
|