Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд: разбить их на четыре непересекающихся непустых подмножества — кластера.
Точки каждого кластера лежат внутри квадрата со стороной 5 условных единиц. Стороны квадратов параллельны координатным осям, а квадраты, содержащие разные кластеры, между собой не пересекаются.
В файле также имеются координаты ровно семи лишних точек — аномалий, возникших в результате помех при передаче данных. Эти точки не принадлежат ни одному из кластеров, и учитывать их не нужно. Гарантируется, что разбиение на четыре кластера и семь аномалий существует и единственно.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек того же кластера минимальна. Для каждого кластера гарантируется единственность его центра. Количества точек во всех четырёх кластерах различны.
Расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле:
d(A, B) = √((x2 − x1)2 + (y2 − y1)2).
Входные данные
В каждой строке файла находятся два вещественных числа — координаты x и y одной точки в условных единицах, разделённые пробелами. Десятичный разделитель — точка. Строки заголовка и строки с количеством точек в файле нет.
Количество точек не превышает 10 000. Абсолютные значения координат не превышают 200. Все точки различны. Порядок строк не определяет принадлежность точки кластеру.
Выполните задание
Определите координаты центров всех четырёх кластеров и количество точек в каждом кластере. Затем вычислите два числа:
- P — расстояние между центром кластера с наименьшим количеством точек и центром кластера с наибольшим количеством точек;
- Q — наибольшее расстояние от центра кластера с наибольшим количеством точек до точки этого же кластера.
В ответе запишите в одной строке два целых числа: сначала целую часть произведения P · 10000, затем целую часть произведения Q · 10000. Округление до ближайшего целого не выполняется. Для выполнения этого задания следует написать программу.
Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.