В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров - прямоугольников размером 3×3 так, что каждая точка попадает ровно в один кластер.
Центроидом кластера называется та из входящих в него точек, для которой минимальна сумма расстояний до всех остальных точек кластера.
Обработка результатов эксперимента включает следующие шаги:
1) кластер, содержащий наибольшее число точек, исключается;
2) определяются центроиды всех оставшихся кластеров;
3) для найденных центроидов вычисляется средняя точка. Средней для группы точек называется точка (не обязательно входящая в группу), координаты которой определяются как средние арифметические значения координат всех точек группы.
В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию. По данному протоколу надо определить среднюю точку центроидов всех кластеров за исключением содержащего наибольшее число точек.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите координаты средней точки по описанным выше правилам.
В ответе запишите четыре числа: сначала (в первой строке) координаты X и Y средней точки для файла A, затем (во второй строке) координаты X и Y средней точки для файла B.
В качестве значения координаты указывайте целую часть от умножения числового значения координаты на 10 000.

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

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

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

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

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

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

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

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

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

Под расстоянием между двумя точками $A(x1,y1)$ и $B(x2,y2)$ понимается манхэттенское расстояние, которое вычисляется по формуле:

d(A,B)=|x2−x1|+|y2−y1|

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

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

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

• $Px$ — среднее арифметическое абсцисс центроидов участков,
• $Py$ — среднее арифметическое ординат центроидов участков.

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

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

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

Расстояние между двумя точками можно вычислить по формуле: $d=\sqrt{(x-a{)}^2+(y-b{)}^2}$, где (x; y) и (a; b) — координаты точек. Гарантируется, что ни одна звезда не находится в диапазоне от одного до трёх радиусов Шварцшильда сразу двух или более чёрных дыр.

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

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

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

(В. Колчев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой 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 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: P_x​ – среднее арифметическое абсцисс центров кластеров, и P_y – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения P_x×1000, затем целую часть абсолютного значения произведения P_y×1000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор не менее чем из 30 соседних звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.
Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x\times 100000$, затем целую часть абсолютного значения произведения $P_y\times 100000$ для файла А, во второй строке – аналогичные данные для файла Б.

(М. Крючков) В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки. После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера. Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева. Расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.
В каждом кластере нужно найти оптимальную точку сбора (центр), такую что суммарная стоимость доставки в это место всех спиленных деревьев данного кластера минимальна. Аномалиями назовём совокупности из не более чем 10 точек, каждая из которых находится на расстоянии более 30 м от точек кластеров. Аномалии в расчётах не учитываются.
В файле A хранятся данные о двух кластерах. Каждый кластер имеет форму прямоугольника размером 100×100 м. Каждая строка файла содержит три характеристики одного дерева: координату x, затем координату y и затем высоту дерева. Количество деревьев в каждом кластере не превышает 1000. В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером не более 100×200 м. Количество точек в каждом кластере не превышает 10 000.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x\times 100000$, затем целую часть абсолютного значения произведения $P_y\times 100000$ для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

(В. Ланская, Р. Ягафаров) В городе X тестируется проект по оптимизации размещения кранов на складах. Оптимальное местоположение для крана (или центроид) будет таким, при котором сумма расстояний Чебышева от этого места до всех других точек на складе была минимальной. Расстояние Чебышева между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $\mathit{\text{d}}(A,B)=max(\mid x_2-x_1\mid ,\mid y_2-y_1\mid )$.
В файле A хранятся данные о двух складских комплексах (кластерах). Каждый комплекс имеет форму прямоугольника размером H = 3 и W = 5. Каждая строка файла содержит координаты одной точки на складе: сначала x, затем y. Количество точек в каждом комплексе не превышает 1000. В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером H = 6 и W = 8. Количество точек в каждом комплексе не превышает 10 000.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x\times 10000$, затем целую часть абсолютного значения произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

(В. Ланская, Р. Ягафаров) Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов на картах планет Информатикус и Алгоритмикус. Район (кластер) – это групп населенных пунктов, которые находятся внутри прямоугольника высотой H и шириной W. Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) – это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле: $\mathit{\text{d}}(A,B)=\mid x_2-x_1\mid +\mid y_2-y_1\mid$
В файле A хранятся данные о точках двух кластеров. В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000. В файле Б той же структуры хранятся данные о точках трёх кластеров. Известно, что количество точек не превышает 10 000. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения $P_x\times 10000$, затем целую часть абсолютного значения произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

(В. Шубинкин) При проведении эксперимента заряженные частицы попадают на чувствительный экран размером 12 на 9 условных единиц. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания в условных единицах. При анализе результатов выделяют кластеры – группы точек на экране, в которые попали частицы. Каждая точка принадлежит только одному кластеру. Минимальное (максимальное) расстояние между кластерами – это минимальное (максимальное) расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая – другому. Расстояние между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
Аномалиями назовём совокупности из не более чем 10 точек, каждая из которых находится на расстоянии более одной условной единицы от точек кластеров. Аномалии в расчётах не учитываются.
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000. В файле Б хранятся данные о трёх кластерах. Известно, что количество точек не превышает 10 000. Структура хранения информации о точках в файле Б аналогична файлу А. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите минимальное ${\mathit{\text{d}}}_{min}$ и максимальное ${\mathit{\text{d}}}_{max}$ расстояния между двумя кластерами. В ответ запишите 4 числа: в первой строке целую часть произведения ${\mathit{\text{d}}}_{min}\times 10000$, затем целую часть произведения ${\mathit{\text{d}}}_{max}\times 10000$ для файла А, во второй строке – аналогичные данные для файла Б.

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

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

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

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

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

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

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

(А. Сражаев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, суммарное гравитационное воздействие которой на звёзды кластера минимально. Гравитационное воздействие между двумя звёздами равно произведению расстояния между ними на модуль разности гравитационного поля этих звёзд. Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
В файле A хранятся данные о звёздах двух кластеров, где H=7, W=8 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y, последним значением указано гравитационное поле g. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1 000.
В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=12 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центроида каждого кластера, затем определите центроид гравитационное поле которого максимально.
В ответе запишите четыре числа: в первой строке сначала целую часть координаты $х\times 1000$, затем целую часть координаты $y\times 1000$ найденного центроида для файла А, во второй строке – аналогичные данные для файла B.

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

(М. Ишимов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{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 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите минимальное возможное количество кластеров для соответствующего набора, а также координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

(М. Ишимов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
В файле A хранятся данные о звёздах двух кластеров, где H=2, W=2 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах пяти кластеров, где H=2, W=2 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

(М. Ишимов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками $A(x_1,y_1)$ и $B(x_2,y_2)$ на плоскости, которое вычисляется по формуле: $\mathit{\text{d}}(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$
В файле A хранятся данные о звёздах трёх кластеров, где H=5, W=5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах четырёх кластеров, где H=5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_1,y_1)$ и $B(x_2,y_2)$ вычисляется по формуле: $\mathit{\text{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 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $P_x$ – среднее арифметическое абсцисс центров кластеров, и $P_y$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $P_x\times 10000$, затем целую часть произведения $P_y\times 10000$ для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

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

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ – среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения $Px\times 100$, затем целую часть произведения $Py\times 100$ для файла А, во второй строке – аналогичные данные для файла Б.

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