Задание 27 ЕГЭ информатика

Как это было в демоверсии 2027

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

Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами от I до VII (в римской системе счисления).

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

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

В каждой строке текстового файла хранится информация об одной частице: координаты $x$ и $y$ , проекции вектора скорости $V_x$ и $V_y$ , масса $m$ и признак.

Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает 10 000. Абсолютная величина каждого числового значения не превышает 100,0.

Известно, что все описанные в файле частицы подразделяются ровно на 4 кластера ( $K = 4$ ) с $R = 2{,}0$ для каждого.

Для каждого кластера определите его центр, затем найдите два числа: $Q_1$ – наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II, и $Q_2$ – максимальное значение кинетической энергии для центра кластера.

В ответе запишите два числа: сначала целую часть произведения $Q_1 \times 10\,000$ , затем целую часть произведения $Q_2 \times 10\,000$ .

Для справки

Кинетическая энергия $E$ частицы массы $m$ , обладающей скоростью $\overline{V} = (V_x;\ V_y)$ вычисляется по формуле:

$E = \frac{1}{2}m\left(V_x^2 + V_y^2\right).$

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

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

Типовой пример организации данных во входном файле

Три строки файла для трёх частиц:

0,67    –2,14    3,0     –4,0    0,2      V
3,14     7,22    3,2      4,3    0,7      II
1,33     5,56    0,00     5,22   0,456    IV

Для частицы из первой строки примера кинетическая энергия равна 2,5.

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

Файл к заданию 27

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 25

Решение и ответ

Считаем энергию каждой частицы (запятую в числах меняем на точку) и сортируем по энергии. Кластеры на числовой прямой — это отрезки, а между ними самые большие разрывы. Для $K = 4$ режем по трём наибольшим промежуткам между соседними энергиями (размах каждого получившегося кластера меньше 2,0 — условие выполнено).
Центр кластера — частица с наименьшей суммой $|E_i - E_j|$ по кластеру (это медиана). $Q_2$ — наибольшая энергия среди четырёх центров.
$Q_1$ — максимум расстояния по координатам $(x, y)$ между двумя частицами с признаком II внутри одного кластера.

from math import dist

p = []
for s in open('27.txt'):
    w = s.replace(',', '.').split()
    if len(w) == 6:
        x, y, vx, vy, m = map(float, w[:5])
        p.append((m * (vx**2 + vy**2) / 2, x, y, w[5]))
p.sort()

# 4 кластера — разрезаем отсортированные энергии по трём самым большим разрывам
cut = sorted(range(1, len(p)), key=lambda i: p[i][0] - p[i - 1][0])[-3:]
b = [0] + sorted(cut) + [len(p)]
q1 = q2 = 0
for i in range(4):
    c = p[b[i]:b[i + 1]]
    center = min(c, key=lambda a: sum(abs(a[0] - e[0]) for e in c))
    q2 = max(q2, center[0])
    two = [a for a in c if a[3] == 'II']
    for a in two:
        for e in two:
            q1 = max(q1, dist(a[1:3], e[1:3]))
print(int(q1 * 10000), int(q2 * 10000))

Ответ: 539936 100704