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

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах двух кластеров, где $H=8$, $W=4$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем вычислите два числа: $P_1$ – сумма абсциссы и ординаты центра кластера с наименьшим количеством точек, и $P_2$ – сумма абсциссы и ординаты центра кластера с наибольшим количеством точек.

Гарантируется, что во всех кластерах количество точек различно.

Для файла B определите координаты центра каждого кластера, затем вычислите два числа: $Q_x$ – абсциссу наиболее отдалённого центра кластера от начала координат, и $Q_y$ – ординату ближайшего центра кластера к началу координат.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения $P_1*10000$, затем абсолютную величину целой части произведения $P_2*10000$; во второй строке - сначала целую часть произведения $Q_x*10000$, затем целую часть произведения $Q_y*10000$.

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

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

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

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

В канун Хэллоуина 2025 года старейшины Гильдии охотников на монстров планирует напасть на жителей заколдованных земель. Для этого они составили мрачную карту, но им мало мрачной карты, им необходимо найти замки на этой карте, так как главная цель уничтожения каждого из замков. Так как Гильдия охотников в первую очередь специализируется на охоте, то у них возникли проблемы с определением замков, но разведать координаты замков с воздуха (именно так они определяли объекты, находящиеся на территории заколдованных земель) невозможно, так как с него все пункты похожие. Именно поэтому, охотники попросили вас помочь им.

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

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

Даны два входных файла (файл A и файл B).

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

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

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

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

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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 = 6$, $W=6$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

​Известно, что в файле B имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

Для файла B найдите два числа: $S'_x$​ - сумма абсцисс точек, которые будут центрами кластеров, если текущие центры убрать из кластеров, и $S'_y$​ - сумма ординат точек, которые будут центрами кластеров, если текущие центры убрать из кластеров.

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке - сначала целую часть произведения $|S_x​| * 10000$, затем целую часть произведения $|S_y|​ * 10 000$; во второй строке - сначала целую часть произведения $|S'_x​| * 10000$, затем целую часть произведения $|S'_y|​ * 10 000$.

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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 = 6$, $W=4.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Известно, что в файле В имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Известно, что в файле B имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

Для файла B найдите два числа: $Q_1$ - расстояние между центрами кластеров с минимальным и максимальным количеством точек, и $Q_2$ - максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров.

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения $P_x*10000$, затем абсолютную величину целой части произведения $P_y*10000$; во второй строке - сначала целую часть произведения $Q_1*10000$, затем целую часть произведения $Q_2*10000$.

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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 = 6$, $W=4.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Известно, что в файле B имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

Для файла B найдите два числа: $Q_1$ - минимальное расстояние между точками, принадлежащими двум различным кластерам, и $Q_2$ - максимальное расстояние между точками, принадлежащими двум различным кластерам.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения $P_x*10000$, затем абсолютную величину целой части произведения $P_y*10000$; во второй строке - сначала целую часть произведения $Q_1*10000$, затем целую часть произведения $Q_2*10000$.

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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 = 6$, $W=4.5$ для каждого кластера. В каждой строке записана информация о расположении на карте одной точки: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Известно, что в файле B имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

Для файла B определите координаты центра каждого кластера, затем найдите два числа: $Q_1$ - минимальное расстояние от центра кластера до начала координат, и $Q_2$ - максимальное расстояние от центра кластера до начала координат.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения $P_x*10000$, затем абсолютную величину целой части произведения $P_y*10000$; во второй строке - сначала целую часть произведения $Q_1*10000$, затем целую часть произведения $Q_2*10000$.

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

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

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

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

Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на $N$ непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером $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 хранятся координаты звёзд, расположенных в 2 кластерах, размеры кластеров $H=5$, $W=4$, не более 1000 точек.

В файле B хранятся координаты звёзд в 3 кластерах, размеры кластеров $H=4$, $W=5$, не более 10000 точек.

Каждая строка файлов A и B содержит два числа — координаты звезды: сначала по оси x, затем по оси $y$.

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

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

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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 = 4$, $W = 4$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Для каждого файла определите $P_s$ — среднее арифметическое плотности всех кластеров, а также $S_p$ — расстояние между центрами кластеров с наибольшей и наименьшей плотностью.

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

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

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

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

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

Компания «СвязьЛес» разрабатывает проект по обеспечению бесперебойной связи в двух труднодоступных лесных массивах. Для этого необходимо установить по одному мощному ретранслятору сигнала в каждом из районов, в местах, где их воздействие будет максимальным. Каждый район состоит из множества лесных участков, представленных в виде геопозиций — точек на плоскости (в декартовой системе координат). Известно, что участки можно разделить на группы лесных кварталов, при этом каждая геопозиция квартала удалена от всех точек других кварталов не менее чем на $R$ условных единиц.

Компания «СвязьЛес» проводит анализ каждой группы (лесного квартала) и выбирает в ней антицентроид — такую геопозицию, сумма расстояний от которой до всех других точек этого квартала максимальна. После этого, опираясь на данные о расположении всех антицентроидов, выбирается финальная точка установки ретранслятора — такая геопозиция, сумма расстояний от которой до всех антицентроидов максимальна. Именно здесь устанавливается ретранслятор. Расстояние между двумя точками вычисляется по формуле Евклида:

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

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

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

Для каждого файла выведите координаты точки установки ретранслятора.

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

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

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

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

Будем называть антицентром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера максимальна. Для каждого кластера гарантируется единственность его антицентра. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах двух кластеров, где $H=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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=11$, $W=11$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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=5$, $W=6$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $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=11$, $W=11$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

Файл В к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21425_27_B.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} * 10000$, затем целую часть произведения $P_{y} * 10000$ для файла А, во второй строке – аналогичные данные для файла B.

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

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

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

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

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах двух кластеров, где $H=6$, $W=6$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

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

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

Чтобы минимизировать количество неприжившихся саженцев кленовых деревьев, решено, что нельзя сажать новые деревья в областях, близлежащих к неплодородным позициям. Такие запретные области определяются как окружности с радиусом $R_1 = 5$, центрами которых являются неплодородные позиции. В конце концов необходимо выделить области, подходящие для посадки, которые характеризуются как окружности с радиусом $R_2 = 7$ с центрами, которые определяются ранее выделенными плодородными позициями. Среди таких областей нужно найти оптимальную: такую, внутри которой находится наибольшее количество плодородных позиций (разумеется, находящихся вне запретных областей). А если оптимальных областей несколько, выбрать область с наибольшей суммой координат.

В файле A в первой строке записаны числа $N$ и $K$. В остальных строках хранятся записи о координатах позиций. Первые $N$ строк содержат координаты (два вещественных числа) плодородных позиций, остальные $K$ – неплодородных. Известно, что количество записей не превышает 1100.

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

Для каждого файла определите координаты центров оптимальной области.

В ответе запишите четыре числа: в первой строке сначала значение произведения первой координаты на $10^{9}$, затем значение произведения второй координаты на $10^{9}$, для файла А, во второй строке – аналогичные данные для файла В.

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

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

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

Файл В к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/20615_27B.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/20497_27.19.A.txt

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

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

Плотностью кластера назовём среднее арифметическое количества точек из этого кластера в единичной окрестности для каждой точки кластера (включая эту точку). Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах четырёх кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

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

Точкой наведения назовём точку, в единичном окрестности от которой находится наибольшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой $x$. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах четырёх кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

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

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

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

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

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

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

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

Средним расстоянием назовём среднее арифметическое расстояние между всеми парами различных точек в кластере. Расстояние между двумя точками на плоскости $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 хранятся данные о звёздах четырёх кластеров, где $H=3$, $W=3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

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

Для каждого файла определите среднее расстояние в каждом кластере, затем вычислите два числа: $S_{min}$ – минимальное среднее расстояние кластера, и $S_{max}$ – максимальное среднее расстояние кластера.

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

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

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

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

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

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

Истинный край кластера – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна. Под расстоянием понимается расстояние Евклида между двумя точками $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.

Эти вычисления помогут экипажу «Интерстеллара-6» безопасно выйти за пределы известных звёздных маршрутов и открыть новые пути в неизведанную часть галактики. Но будьте осторожны — ошибка может привести корабль в ловушку гравитации чёрной дыры!

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

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

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

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

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

Центроид - это среднее арифметическое положение всех точек на поверхности фигуры.

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

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

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

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

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

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

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

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

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

Будем называть медианой по $x$ такую точку, что половина (кроме самой точки) точек по значению абсциссы будет больше её абсциссы, а половина меньше. А медианой по $y$ аналогичное значение в ординатах. Гарантируется единственной такого значения в каждом кластере. Так же гарантируется, что в каждом кластере нечётное количество точек.

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

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

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

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

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

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

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

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

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

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $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/19715_27.21.A.txt

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

Компания «Энергосеть» занимается оптимизацией энергоснабжения в нескольких регионах. Для этого нужно определить местоположение главных трансформаторных узлов, которые обеспечат минимальные потери при распределении энергии. В каждом регионе имеются несколько подрегионов, каждый из которых характеризуется тем, что расстояние от любой точки в подрегионе до точки из другого подрегиона не менее $R$ условных единиц.

Необходимо определить место для трансформаторного узла, которое находится за два шага: сначала для каждого подрегиона нужно найти его центр нагрузки — такую точку в подрегионе, от которой суммарное расстояние до всех остальных точек подрегиона минимально. Затем, учитывая данные о центрах нагрузки всех подрегионов, найти центральный трансформаторный узел — такая точка в регионе, от которой суммарное расстояние до всех центров нагрузки минимально. Если подходящих точек несколько, выбирается та, у которой абсцисса наименьшая. Расстояние между двумя точками $(x_1, y_1)$ и $(x_2, y_2)$ на плоскости вычисляется по формуле Евклида:

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

Файл A содержит данные о точках двух подрегионов. Файл B содержат данные о точках трёх подрегионов. В первой строке каждого файла записано значения $R$. В каждой из следующих строк записаны координаты $x$ и $y$ очередной точки. Количество точек в файле A не превышает 1000, в B не превышает 10000.

Для каждого подрегиона определить координаты центрального трансформаторного узла.

В ответе укажите четыре целых числа: в первой строке - ближайшие целые числа значений произведения координаты $x$ узла на 10000 и координаты $y$ узла на 10000 для региона А; во второй строке - аналогичные данные для региона В.

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

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