Задание №27: Кластерный анализ и геометрические алгоритмы

(В. Шубинкин) При проведении эксперимента заряженные частицы попадают на чувствительный экран размером 12 на 9 условных единиц. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания в условных единицах. При анализе результатов выделяют кластеры – группы точек на экране, в которые попали частицы. Каждая точка принадлежит только одному кластеру. Минимальное (максимальное) расстояние между кластерами – это минимальное (максимальное) расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому. Расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:
Аномалиями назовём совокупности из не более чем 10 точек, каждая из которых находится на расстоянии более одной условной единицы от точек кластеров. Аномалии в расчётах не учитываются. Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000. В файле Б хранятся данные о трёх кластерах. Известно, что количество точек не превышает 10 000. Структура хранения информации о точках в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите минимальное d_min и максимальное d_max расстояния между двумя кластерами. В ответ запишите 4 числа: в первой строке целую часть произведения d_min × 10 000, затем целую часть произведения d_max × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.