Банк заданий
ЕГЭ по информатике Задание №27 Анализ данных, Кластеризация

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри параллелограмма. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_{1},y_{1})$ и $B(x_{2}, y_{2})$ на плоскости, которое вычисляется по формуле:

$d(A,B)=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах шести кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_{x}$ – среднее арифметическое абсцисс центров кластеров, и $P_{y}$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_{x} * 10000$, затем целую часть абсолютного значения произведения $P_{y} * 10000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19567_27.13.A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19567_27.13.B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри треугольника. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный край кластера – это одна из звёзд в кластере, сумма расстояний от которой до всех остальных звёзд кластера максимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_{1}, y_{1})$ и $B(x_{2}, y_{2})$ на плоскости, которое вычисляется по формуле:

$d(A,B)=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$.

Аномалиями назовём звёзды, находящиеся на расстоянии более одной условной единицы от звёзд кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах четырёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты края каждого кластера, затем вычислите два числа: $T_{x}$ – среднее арифметическое абсцисс краев кластеров, и $T_{y}$ – среднее арифметическое ординат краев кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $T_{x} * 10000$, затем целую часть абсолютного значения произведения $T_{y} * 10000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19566_27.17.A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19566_27.17.B.txt

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле:

$d(A,B)=\sqrt{(x_1 - x_2)^{2} + (y_1 - y_2)^{2}}$.​

В файле A хранятся данные о звёздах десяти кластеров, где $H=2$, $W=2$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах ста кластеров, где $H=2$, $W=2$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$​ – среднее арифметическое абсцисс центров кластеров, и $P_y$​ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x*10000$, затем целую часть произведения $P_y*10000$ для файла А, во второй строке – аналогичные данные для файла B.

Гарантируется, что расстояние между любыми двумя точками разных кластеров превышает 1.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19153_27_B.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/19153_27_A.txt

В администрации резиденции Деда Мороза проводится активное обсуждение вопроса эффективности перевозки мириад подарков в канун волшебного Нового Года. Снегурочка настаивает на немедленном внедрении передовых технологий: «Старый мешок с письмами никуда не годится — в этой куче адресов невозможно разобраться, да и Дед уже не тот, даже таблетки не помогают. Если мы срочно не решим эту проблему, наш дорогой Дед Мороз скоро превратится в Санта Клауса! Министерство культуры РФ такое точно не одобрит». В сказочной резиденции с женщинами спорить не принято, тем более с такими молодыми и горячими, как прелестная Снегурочка. Да и аргументы в этот раз звучат убедительно...

Отдел аналитики данных возложил решение обозначенной ранее проблемы на могучие плечи СнегПрогов (снеговиков-программистов). СнегПроги предложили простую концепцию: разделить письма на группы (города) по характеристике места жительства (геопозиции) их отправителей. Благодаря этому гениальному подходу Деду Морозу не придется по сто раз перемещаться между Москвой и Владивостоком, ведь он сможет переходить к доставке подарков по Москве только после того, как развезет все подарки владивостокцам. И Декабрь, Январь и Февраль точно останутся благодарны своему хозяину. К тому же получится сэкономить на бензине, что в наше время совсем не дурно!

Одним городом СнегПроги решили считать такую группу геопозиций (точек, определенных по двум координатам $x$ и $y$), в которой любая из геопозиций удалена от геопозиции из другой группы хотя бы на $E = 20$ у.е. (условных единиц). А метрикой расстояния между двумя точками (геопозициями) уже традиционно стала формула Евклида:

$d(A, B) =$ $\sqrt{(x_{2} - x_{1})^2 + (y_{2} - y_{1})^2}$.

Помогите СнегПрогам найти оптимальные геопозиции в каждом городе для открытия в них новых филиалов резиденции. Лучшим местом будет считаться такая геопозиция, суммарное расстояние от которой до всех других геопозиций в этом же городе минимально. Если у вас все получится, СнегПроги получат в подарок от Деда Мороза новые чудо-компьютеры, сделанные из льдинок высочайшего качества. А вам в таком случае полагается хорошее настроение =)

В файле A хранятся записи об адресах первой партии полученных писем, образующих 2 города. В каждой строке записана информация о двух показателях геопозиции конкретного письма: сначала координата $x$, затем координата $y$. Известно, что количество записей не превышает 2200.

В файле B хранятся записи об адресах второй партии полученных писем, образующих 3 города. Известно, что количество записей не превышает 15500. Структура хранения информации в файле B аналогична файлу А.

Для каждого файла определите координаты новых филиалов резиденции для всех городов, а затем вычислите два числа: $S_x$​ – среднее арифметическое абсцисс этих филиалов, и $S_y$​ – среднее арифметическое их ординат.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения $S_x​$, затем целую часть абсолютного значения $S_y​$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18884_27_A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18884_27_B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18678_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18678_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18677_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18677_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18676_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18676_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x * 100 000$, затем целую часть абсолютного значения произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18675_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18675_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18630_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18630_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18629_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18629_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18628_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18628_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18627_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18627_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18626_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18626_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18625_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18625_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18624_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18624_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 100 000$, затем целую часть произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18623_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18623_27B.txt

В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.

По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров - прямоугольников размером $3*3$ так, что каждая точка попадает ровно в один кластер.

Центроидом кластера называется та из входящих в него точек, для которой минимальна сумма расстояний до всех остальных точек кластера.

Обработка результатов эксперимента включает следующие шаги:

1) кластер, содержащий наибольшее число точек, исключается;

2) определяются центроиды всех оставшихся кластеров;

3) для найденных центроидов вычисляется средняя точка.

Средней для группы точек называется точка (не обязательно входящая в группу), координаты которой определяются как средние арифметические значения координат всех точек группы.

В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты $X$ и $Y$ точки, соответствующей одному испытанию. По данному протоколу надо определить среднюю точку центроидов всех кластеров за исключением содержащего наибольшее число точек.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите координаты средней точки по описанным выше правилам.

В ответе запишите четыре числа: сначала (в первой строке) координаты $X$ и $Y$ средней точки для файла A, затем (во второй строке) координаты $X$ и $Y$ средней точки для файла B.

В качестве значения координаты указывайте целую часть от умножения числового значения координаты на 10000.

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18622_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18622_27B.txt

Ведущие специалисты отдела бизнес-аналитики торгового маркетплейса «Ozonyol» собирают статистику и изучают предпочтения покупателей за период летних и осенних продаж. Перед ними стоит задача – проанализировать рынок и сделать выводы об уровне спроса на товары различных категорий для выделения наиболее перспективных траекторий развития площадки с привлечением инвестиционных средств.

По итогам сбора информации имеется набор данных, включающий записи о товарах, каждый из которых содержит три показателя – номер сегмента товара, характеризующий его расположение на сайте, коэффициент успешных конверсий и уровень заинтересованности покупателей, выраженный в коэффициенте их активности. Общий спрос на товар вычисляется как среднее арифметическое второго и третьего показателей.

На основании полученной информации строится графический отчёт, отражающий общий спрос на товар в зависимости от его номера сегмента, в котором записи, лежащие в области окружности с радиусом $R$, выделяются в отдельные кластеры. В итоге решено привлекать средства на продвижение товаров только из кластеров, содержащих хотя бы $K$ записей, причем первые вложения направить в товары-медоиды.

Медоидом (центром) кластера называется такая запись о товаре, суммарное расстояние от которой до других записей в кластере минимально. Метрикой расстояния между двумя записями $A(x_1, y_1)$ и $B(x_2, y_2)$ является формула Евклида:

$d(A, B) = \sqrt{(x_{2} - x_{1})^2 + (y_{2} - y_{1})^2}$ .

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

В файле A в первой строке записаны числа $R$ и $K$. В остальных строках хранятся записи о товарах за период летних продаж, образующих 3 кластера. В каждой строке записана информация о трех показателях конкретного товара: сначала номер сегмента товара, затем коэффициент успешных конверсий и коэффициент активности. Известно, что количество записей не превышает 1100.

В файле B хранятся записи о товарах за период осенних продаж, образующих 6 кластеров, и соответствующие осенним продажам числа $R$ и $K$. Известно, что количество записей не превышает 11000. Структура хранения информации о товарах в файле B аналогична файлу А.

Для каждого файла определите координаты медоидов (центров) всех кластеров, для продвижения которых будут привлечены инвестиционные средства, а затем вычислите два числа: $S_x$​ – среднее арифметическое абсцисс центров кластеров, и $S_y$​ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $S_x​*100000$, затем целую часть произведения $S_y*100000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18585_27_A.txt

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18585_27_B.txt

Популярная компания по доставке продуктов «Быстрокат» расширяется и хочет открыть новые филиалы в двух густонаселенных районах города. Для открытия отдела логистам необходимо выбрать самую подходящую геолокацию для оптимизации организации процессов по координации и доставке товаров, для чего им нужно проанализировать множество жилых единиц (геопозиций). Каждый район состоит из нескольких микрорайонов, включающих в себя некоторое количество геопозиций. Известно, что каждый микрорайон характеризуется тем, что любая из его геопозиций удалена от любой геопозиции из других микрорайонов хотя бы на $R$ у.е. (условных единиц). Для анализа данных используется предоставленный набор вещественных точек (геопозиций), размещенных на декартовой оси координат. Они характеризуют все геопозиции конкретного района, который представляет собой квадрат размером $10$ у.е. (условных единиц). С целью определить оптимальную геолокацию для открытия филиала логисты вычисляют медоид (райцентр) каждого микрорайона, который определяется как такая геопозиция внутри одного микрорайона, суммарное расстояние от которой до всех других геопозиций этого же микрорайона минимально. Затем специалисты определяют конечный медоид, опираясь на данные о расположении ранее найденных медоидов, – такую геопозицию, суммарное расстояние от которой до всех медоидов минимально. Именно в этой геопозиции и будет затем открыт новый филиал. При проведении расчетов также исключаются аномальные геопозиции, случайно попавшие в представленный набор данных. Они определяются как точки, расстояние от которых до любой другой точки в наборе данных превышает $K$ у.е. (условных единиц). Метрикой расстояния между двумя геопозициями (точками) $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости является формула Евклида:

$d(A, B) =$ $\sqrt{(x_{2} - x_{1})^2 + (y_{2} - y_{1})^2}$.

В файле A хранятся данные обо всех геопозициях первого района. В первой строке записаны значения $R$ и $K$ для этого района. В каждой из следующих строк записана информация о расположении в районе одной геопозиции: сначала координата $x$, затем координата $y$. Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество геопозиций не превышает 2000.

В файле B хранятся данные обо всех геопозициях второго района. В первой строке записаны значения $R$ и $K$ для этого района. Известно, что количество геопозиций не превышает 30000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите геопозицию, в которой будет открыт филиал.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения координаты $x$ этой геопозиции на 10000, затем целую часть произведения координаты $y$ этой геопозиции на 10000 для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18390_27_A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18390_27_B.txt

На складе с автоматической системой управления работают роботы, которые собирают грузы, расположенные на разных участках склада. Склад представляет собой прямоугольную сетку высотой $H$ и шириной $W$. Каждый робот может перемещаться только вдоль осей сетки (вверх, вниз, влево, вправо), поэтому для оценки расстояний между объектами используется манхэттенское расстояние. Под расстоянием между двумя точками $A(x1, y1)$ и $B(x2, y2)$ понимается манхэттенское расстояние, которое вычисляется по формуле:

$d(A, B) = |x_2 - x_1| + |y_2 - y_1|$.

Группа инженеров решила оптимизировать работу роботов, минимизировав общее время сбора грузов. Для этого необходимо определить координаты груза в каждом участке склада, для которой сумма расстояний от неё до всех грузов на участке будет минимальной. Эта точка называется центроидом. Робот, находящийся в центроиде, сможет быстрее собрать все грузы на своём участке.

В файле A хранятся данные о расположении грузов на двух участках склада, где каждый участок имеет размеры $H = 10$ и $W = 20$. В каждой строке записана информация о расположении одного груза: сначала координата $x$, затем координата $y$. Количество грузов в файле не превышает 1000.

В файле B хранятся данные о грузах на трёх участках склада, где каждый участок также имеет размеры $H = 10$ и $W = 20$. Количество грузов в файле не превышает 10000. Структура хранения информации о грузах в файле B аналогична файлу A.

Для каждого файла определите координаты центра каждого участка (центроида), а затем вычислите два числа: $P_x$ — среднее арифметическое абсцисс центроидов участков, и $P_y$ — среднее арифметическое ординат центроидов участков.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x * 1000$ затем целую часть абсолютного значения произведения $P_y * 1000$ для файла A; во второй строке — аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18314_27_A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18314_27_B.txt

Радиус Шварцшильда — это характеристика черной дыры, определяющая её границу, которую часто называют горизонтом событий. Учёный изучает вращение звёзд (точек) вокруг чёрных дыр и рассматривает те звёзды, которые находятся в диапазоне от одного до трёх радиусов Шварцшильда.

Назовём расстоянием между чёрной дырой и звездой — расстояние от звезды до горизонта событий рассматриваемой чёрной дыры. Расстояние между двумя точками можно вычислить по формуле:

$d = \sqrt{(x - a)^{2} + (y - b)^2}$,

где $(x; y)$ и $(a; b)$ — координаты точек. Гарантируется, что ни одна звезда не находится в диапазоне от одного до трёх радиусов Шварцшильда сразу двух или более чёрных дыр.

В файлах A и B хранятся данные о чёрных дырах и звёздах. В первой строке указано число $n$ — количество чёрных дыр. В последующих $n$ строках указаны три числа: первое и второе — координаты $x$ и $y$ (в условных единицах) центра чёрной дыры соответственно, третье — радиус Шварцшильда (в условных единицах) для этой чёрной дыры. В каждой последующей строке записана информация о расположении одной звезды — сначала координата x, затем координата $y$.

Известно, что количество звёзд в файле А не превышает 1000, а в файле B — 10000.

Для каждой чёрной дыры найдите среднее арифметическое расстояние от неё до звёзд, находящихся в диапазоне от одного до трёх радиусов Шварцшильда соответствующей чёрной дыры. Полученные результаты умножьте на 1000 и отбросьте все оставшиеся десятичные знаки.

В ответе запишите сначала наибольшее, а затем наименьшее значения для файла А. Затем запишите подсчитанные значения для файла B в том же порядке.

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18184_27_A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18184_27_B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой $H$ и шириной $W$. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле:

$d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.​

В файле A хранятся данные о звёздах двух кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где $H=3$, $W=3$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_{x}$​ – среднее арифметическое абсцисс центров кластеров, и $P_{y}$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_{x}*1000$, затем целую часть абсолютного значения произведения $P_{y}*1000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18150_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18150_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x * 100 000$, затем целую часть абсолютного значения произведения $P_y * 100 000$ для файла А, во второй строке – аналогичные данные для файла B.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18056_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18056_27B.txt

При проведении эксперимента заряженные частицы попадают на чувствительный экран размером 12 на 9 условных единиц. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания в условных единицах. При анализе результатов выделяют кластеры – группы точек на экране, в которые попали частицы. Каждая точка принадлежит только одному кластеру.

Минимальное (максимальное) расстояние между кластерами – это минимальное (максимальное) расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2,y_2)$ вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

Аномалиями назовём совокупности из не более чем 10 точек, каждая из которых находится на расстоянии более одной условной единицы от точек кластеров. Аномалии в расчётах не учитываются.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество точек не превышает 1000.

В файле B хранятся данные о трёх кластерах. Известно, что количество точек не превышает 10000. Структура хранения информации о точках в файле B аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите минимальное $\textit{d}_{min}$ и максимальное $\textit{d}_{max}$ расстояния между двумя кластерами.

В ответ запишите 4 числа: в первой строке целую часть произведения $\textit{d}_{min} * 10000$, затем целую часть произведения $\textit{d}_{max} * 10000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18052_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18052_27B.txt

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$ на плоскости, которое вычисляется по формуле:

$\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$ (в условных единицах). Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x * 10 000$, затем целую часть произведения $P_y * 10 000$ для файла А, во второй строке – аналогичные данные для файла B.

Возможные данные одного из файлов проиллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемых файлов. 

Файл А к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18051_27A.txt

Файл B к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/18051_27B.txt