Задача #2632

(Л. Шастин) Ведущие специалисты отдела бизнес-аналитики торгового маркетплейса «Ozonyol» собирают статистику и изучают предпочтения покупателей за период летних и осенних продаж. Перед ними стоит задача – проанализировать рынок и сделать выводы об уровне спроса на товары различных категорий для выделения наиболее перспективных траекторий развития площадки с привлечением инвестиционных средств. По итогам сбора информации имеется набор данных, включающий записи о товарах, каждый из которых содержит три показателя – номер сегмента товара, характеризующий его расположение на сайте, коэффициент успешных конверсий и уровень заинтересованности покупателей, выраженный в коэффициенте их активности. Общий спрос на товар вычисляется как среднее арифметическое второго и третьего показателей. На основании полученной информации строится графический отчёт, отражающий общий спрос на товар в зависимости от его номера сегмента, в котором записи, лежащие в области окружности с радиусом $R$, выделяются в отдельные кластеры. В итоге решено привлекать средства на продвижение товаров только из кластеров, содержащих хотя бы $K$ записей, причем первые вложения направить в товары-медоиды. Медоидом (центром) кластера называется такая запись о товаре, суммарное расстояние от которой до других записей в кластере минимально. Метрикой расстояния между двумя записями $A(x1,y1)$ и $B(x2,y2)$ является формула Евклида: $d(A,B)=$ $\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.

Примечание. Гарантируется, что каждый товар принадлежит только одному из кластеров.

В файле A в первой строке записаны числа $R$ и $K$. В остальных строках хранятся записи о товарах за период летних продаж, образующих 3 кластера. В каждой строке записана информация о трех показателях конкретного товара: сначала номер сегмента товара, затем коэффициент успешных конверсий и коэффициент активности. Известно, что количество записей не превышает 1100. В файле Б хранятся записи о товарах за период осенних продаж, образующих 6 кластеров, и соответствующие осенним продажам числа $R$ и $K$. Известно, что количество записей не превышает 11 000. Структура хранения информации о товарах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты медоидов (центров) всех кластеров, для продвижения которых будут привлечены инвестиционные средства, а затем вычислите два числа: $Sx$​ – среднее арифметическое абсцисс центров кластеров, и $Sy$​ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения $Sx\times 100000$, затем целую часть произведения $Sy\times 100000$ для файла А, во второй строке – аналогичные данные для файла Б.