ЕГЭ-27. Анализ данных. Кластеризация

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

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения \(P_1 \times 10\,000\), затем целую часть произведения \(P_2 \times 10\,000\); во второй строке – сначала \(Q_1\), затем \(Q_2\).

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

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

Для файла A определите координаты центра каждого кластера, затем найдите два числа: \(P_1\) – минимальное расстояние от точки с координатами (1,0; 1,0) до центра кластера, и \(P_2\) – максимальное расстояние от этой же точки до центра кластера.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: \(Q_1\) – в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 1,2 от центра кластера, и \(Q_2\) – в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 0,75 от центра кластера. Гарантируется, что во всех кластерах количество точек различно.

(ЕГЭ-2025) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Каждый кластер имеет форму прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Центр кластера ‐ это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. В файле А хранятся данные о звёздах 2-х кластеров, для которых H=6 и W=4,5. В файле B хранятся данные о звёздах 3-х кластеров, для которых H=5 и W=6. В файле Б имеются координаты ровно «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px - максимальную из абсцисс центров кластеров, и Py ‐ максимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Qx ‐ разность абсцисс центров кластеров с минимальным и максимальным количеством точек, и Qy ‐ разность ординат центров кластеров с минимальным и максимальным количеством точек. Гарантируется, что во всех кластерах количество точек различно.

Исходные данные находятся в файлах 27-96a.txt и 27-96b.txt.

В ответе запишите четыре числа: в первой строке ‐ сначала целую часть абсолютного значения произведения Px × 10000, затем целую часть абсолютного значения произведения Py × 10 000; во второй строке ‐ сначала целую часть абсолютного значения произведения Qx × 10 000, затем целую часть абсолютного значения произведения Qy × 10 000.

(В. Глезденев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Каждый кластер можно вписать в круг радиуса R. Центр кластера ‐ это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. В файле А хранятся данные о звёздах 2-х кластеров, для которых R = 3. В файле B хранятся данные о звёздах 3-х кластеров, для которых R = 4. Для каждого файла определите центры всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс всех центров, и P_y ‐ среднее арифметическое ординат всех центров.

Исходные данные находятся в файлах 27-92a.txt и 27-92b.txt.

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

(В. Глезденев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Каждый кластер имеет форму круга радиуса R, причём эти круги между собой не пересекаются. Центр кластера ‐ это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Аномалиями назовём точки, находящиеся вне круга радиуса R от центра любого кластера. При расчётах аномалии учитывать не нужно. В файле А хранятся данные о звёздах 2-х кластеров, для которых R = 3. В файле B хранятся данные о звёздах 3-х кластеров, для которых R = 4. Для каждого файла определите центры всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс всех центров, и P_y ‐ среднее арифметическое ординат всех центров.

Исходные данные находятся в файлах 27-91a.txt и 27-91b.txt.

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

(В. Глезденев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Каждый кластер имеет форму сектора круга с радиусом R и центральным углом H = 70°, причём эти сектора между собой не пересекаются. Центр кластера ‐ это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. В файле A хранятся данные о звёздах 3-х кластеров, для которых R = 10. В файле Б хранятся данные о звёздах 4-х кластеров, для которых R = 12. Для каждого файла определите центры всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс всех центров, и P_y ‐ среднее арифметическое ординат всех центров.

Исходные данные находятся в файлах 27-89a.txt и 27-89b.txt.

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

(В. Глезденев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Каждый кластер имеет форму сектора круга радиусом R = 10 и центральным углом H = 60°, причём эти сектора между собой не пересекаются. Центр кластера ‐ это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Для каждого файла определите центры всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс всех центров, и P_y ‐ среднее арифметическое ординат всех центров.

Исходные данные находятся в файлах 27-88a.txt и 27-88b.txt.

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

(В. Лашин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Центроидом кластера назовём точку, абсцисса и ордината которой ‐ средние арифметические абсцисс и ординат всех точек кластера, соответственно. Для каждого файла определите центроиды всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс всех центроидов, и P_y ‐ среднее арифметическое ординат всех центроидов.

Исходные данные находятся в файлах 27-87a.txt и 27-87b.txt.

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

(В. Лашин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... X-медианой кластера назовём такую абсциссу точки кластера, что в этом кластере количество точек с абсциссами, меньшими x-медианы, равно количеству точек с абсциссами, большими x-медианы. Y-медиана кластера определяется аналогично для ординат точек. Для каждого файла определите x-медианы и y-медианы всех кластеров, затем вычислите два числа: P_x ‐ среднее арифметическое x-медиан, и P_y ‐ среднее арифметическое y-медиан.

Исходные данные находятся в файлах 27-86a.txt и 27-86b.txt.

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

(В. Лашин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Крайней точкой кластера назовём такую точку, что расстояние от неё до ближайшей точки другого кластера минимально. В системе из N кластеров каждый кластер имеет N-1 крайних точек. Для каждого файла найдите координаты всех крайних точек, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс этих точек, и P_y ‐ среднее арифметическое ординат этих точек.

Исходные данные находятся в файлах 27-85a.txt и 27-85b.txt.

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

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

Исходные данные находятся в файлах 27-84a.txt и 27-84b.txt.

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

(А. Кабанов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Изолированной точкой назовём точку, в единичной окрестности которой находится наименьшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой y. Для каждого файла определите координаты изолированной точки каждого кластера, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс изолированных точек кластеров, и P_y ‐ среднее арифметическое ординат изолированных точек кластеров.

Исходные данные находятся в файлах 27-82a.txt и 27-82b.txt.

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

(А. Кабанов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Точкой наведения назовём точку, в единичной окрестности которой находится наибольшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой x. Для каждого файла определите координаты точки наведения каждого кластера, затем вычислите два числа: P_x ‐ среднее арифметическое абсцисс точек наведения кластеров, и P_y ‐ среднее арифметическое ординат точек наведения кластеров.

Исходные данные находятся в файлах 27-81a.txt и 27-81b.txt.

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

(А. Кабанов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Средним расстоянием S назовём среднее арифметическое расстояние между всеми парами различных точек в кластере. Для каждого файла определите среднее расстояние в каждом кластере, затем вычислите два числа: S_min ‐ минимальное среднее расстояние кластера, и S_max ‐ максимальное среднее расстояние кластера.

Исходные данные находятся в файлах 27-80a.txt и 27-80b.txt.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения S_min × 100 000, затем целую часть абсолютного значения произведения S_max × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

(А. Кабанов) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... Диаметром кластера D назовём максимальное расстояние между двумя точками в кластере. Для каждого файла определите диаметр каждого кластера, затем вычислите два числа: D_min ‐ минимальный диаметр кластера, и D_avg ‐ среднее арифметическое диаметров кластеров.

Исходные данные находятся в файлах 27-79a.txt и 27-79b.txt.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения D_min × 100 000, затем целую часть абсолютного значения произведения D_avg × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд ‐ это набор звёзд (точек) на графике, лежащий внутри круга некоторого радиуса. Центр кластера ‐ это одна из звёзд, среднее расстояние от которой до всех остальных звёзд кластера минимально. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).Требуется найти радиусы всех кластеров и определить их среднее арифметическое R.

Исходные данные находятся в файлах 27-76a.txt и 27-76b.txt.

В ответе запишите числа: сначала целую часть абсолютного значения произведения R × 10 000 для файла, затем аналогичное значение для файла Б.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд ‐ это набор звёзд (точек) на графике, лежащий внутри круга некоторого радиуса. Центр кластера ‐ это одна из звёзд, среднее расстояние от которой до всех остальных звёзд кластера минимально. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\). Требуется найти радиусы всех кластеров и определить их среднее арифметическое R.

Исходные данные находятся в файлах 27-75a.txt и 27-75b.txt.

В ответе запишите числа: сначала целую часть абсолютного значения произведения R × 10 000 для файла, затем аналогичное значение для файла Б.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд ‐ это набор звёзд (точек) на графике, лежащий внутри круга некоторого радиуса. Центр кластера ‐ это одна из звёзд, среднее расстояние от которой до всех остальных звёзд кластера минимально. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\). Радиус кластера ‐ это максимальное расстояние от какой-либо звезды, входящей в кластер, до центра этого кластера. Каждая звезда обязательно принадлежит только одному из кластеров; ближайшие точки разных кластеров отстоят друг от друга не менее, чем на единичное расстояние. Требуется найти радиусы всех кластеров и определить их среднее арифметическое R.

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

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

В файле Б аналогичной структуры хранятся данные о звёздах четырёх кластеров; количество звёзд не превышает 10 000.

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

В ответе запишите числа: сначала целую часть абсолютного значения произведения R × 10 000 для файла, затем аналогичное значение для файла Б.

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

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

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

Выходные данные
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

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

Исходные данные находятся в файлах 27-72a.txt и 27-72b.txt.

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

Исходные данные находятся в файлах 27-69a.txt и 27-69b.txt.