Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на \(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\) для каждого кластера. Известно, что количество звёзд не превышает \(10~000.\) Структура хранения информации о звездах в файле B аналогична файлу A.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) — среднее арифметическое абсцисс центров кластеров, и \(P_y\) — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения \(P_x \times 10000,\) затем абсолютное значение целой части произведения \(P_y \times 10000\) для файла A, во второй строке — аналогичные данные для файла B. Возможные данные одного из файлов иллюстрированы графиком.

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

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала абсолютное значение целой части произведения \(P_x \times 10~000,\) затем абсолютное значение целой части произведения \(P_y \times 10~000\) для файла А, во второй строке – аналогичные данные для файла Б.

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

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) — среднее арифметическое абсцисс центров кластеров, и \(P_y\) — среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(|P_x| \times 10~000,\) затем целую часть произведения \(|P_y| \times 10~000\) для файла А, во второй строке — аналогичные данные для файла Б. Возможные данные одного из файлов иллюстрированы графиком.

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

(Д. Бахтиев) Во время геофизического исследования был построен план подземного участка местности. На карте, спроецированной на плоскость с декартовой системой координат, отмечены сигналы, полученные от различных объектов. Каждая точка на карте соответствует зарегистрированному сигналу с координатами \(x\) и \(y\) (в условных единицах).

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

Будем называть центром кластера такую его точку, сумма расстояний от которой до всех остальных точек кластера минимальна. Расстояние между двумя точками на плоскости \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$ В процессе анализа выяснилось, что среди сигналов присутствуют аномальные шумы. Это — ложные сигналы, вызванные помехами. Известно следующее:

• Учёный не знает координат аномалий заранее;
• Однако он знает, что:
  • Аномалии не принадлежат ни одному кластеру
  • Для любой пары настоящих точек одного кластера можно найти последовательность \(A = P_1, \, P_2, \, \ldots , P_k = B,\) где расстояние между соседними сигналами \(P_i\) и \(P_{i+1}\) меньше \(1.\)
  • В единичной окрестности любой настоящей точки нет ни одной аномальной;
  • В любом кластере более \(5\) точек;
  • Количество аномалий не более \(20\) для каждого из файлов.

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

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

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютно значения произведения \(P_x \times 10000,\) затем целую часть абсолютного значения произведения \(P_y \times 10000\) для файла A, во второй строке — аналогичные данные для файла B.

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

Будем называть ядром кластера точку этого кластера, сумма расстояний от которой до \(K=10\) самых удалённых от неё и до \(V=5\) самых близких к ней точек этого же кластера минимальна. Для каждого кластера гарантируется единственность его ядра. Расстояние между двумя точками на плоскости \(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=5,\) \(W=5\) для каждого кластера. Известно, что количество звёзд не превышает \(10~000.\) Структура хранения информации о звездах в файле B аналогична файлу A.

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

В ответе запишите четыре числа: в первой строке сначала целая часть абсолютного значения произведения \(P_x \times 10000,\) затем целая часть абсолютного значения произведения \(P_y \times 10000\) для файла A, во второй строке — аналогичные данные для файла B.

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

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

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

(Д. Бахтиев) Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на \(N\) непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером \(H \times W,\) при этом прямоугольники не перекрываются. Стороны прямоугольников не обязаны быть параллельны осям координат. Гарантируется, что такое разбиение единственно для заданных размеров прямоугольников. Расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$ A(x_1, \, y_1) = \sqrt{(x_2 - y_1)^2 + (y_2 - y_1)^2} $$ Центром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера минимальна. Антицентром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера максимальна.

Входные данные

Файл A: содержит координаты звёзд, расположенных в \(2\) кластерах, размеры кластеров \(H = 5,\) \(W = 4,\) не более \(1000\) точек.

Файл В: содержит координаты звёзд в \(3\) кластерах, размеры кластеров \(H = 4,\) \(W =5,\) не более \(10~000\) точек.

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

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

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения \(P_x \times 10000,\) затем целую часть абсолютного значения произведения \(S_y \times 10000\) для файла A, во второй строке — аналогичные данные для файла B.

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

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

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