Задание 27. Информатика. ЕГЭ 2027. Шастин. 30.09.2026

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

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

Будем называть центром кластера такую его частицу, для которой сумма Манхэттенских расстояний до всех остальных частиц этого же кластера минимальна. Если таких частиц в кластере несколько, центром считается частица с наибольшей координатой \(y.\)

В каждой строке текстового файла хранится информация об одной частице: координаты \(x\) и \(y,\) проекции вектора скорости \(V_x,\) и \(V_y,\) масса \(m\) и признак. Значения даны в одинаковых для всех частиц единицах измерения, обозначения единиц измерения в файле не приводятся. Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции. Количество строк в файле не превышает \(10~000.\) Абсолютная величина каждого числового значения не превышает \(100{,}0.\) Известно, что все описанные в файле частицы подразделяются ровно на пять кластеров \((K = 5)\) с \(R = 2{,}5\) для каждого.

Для каждого кластера определите его центр, затем найдите два числа: \(Q_1\) — сумму модулей скоростей \(\sqrt{V_x^2 + V_y^2}\) всех найденных центров кластеров и \(Q_2\) – наименьшее евклидово расстояние между двумя разными частицами одного кластера, имеющими признак \(III\) или \(V,\) при условии, что угол между их векторами скоростей превышает \(90^\circ\) (скалярное произведение строго отрицательно: \(V_{x1} \cdot V_{x2} + V_{y1} \cdot V_{y2} < 0).\)

В ответе: целая часть \(Q_1 \cdot 10~000,\) затем \(Q_2 \cdot 10~000.\)

Для справки

Модуль момента импульса частицы массы \(m,\) находящейся в точке с координатами \(x\) и \(y\) и обладающей скоростью \(\vec{V} = (V_x; \, V_y),\) вычисляется по формуле: $$L = m \cdot \left| x \cdot V_y - y \cdot V_x \right|$$ Манхэттенское расстояние между двумя точками на плоскости \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$d_M (A, \, B) = \left| x_1 - x_2 \right| + \left| y_1 - 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}$$

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

Три строки файла для трёх частиц:
$$ \begin{array}{l l l l l l } 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 & III \end{array} $$

Для частицы из первой строки примера момент импульса \(L\) равен \(0{,}748.\)

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

from math import dist

def manh(v1, v2):
    return abs(v1[0] - v2[0]) + abs(v1[1] - v2[1])

def scal(v1, v2):
    return v1[0] * v2[0] + v1[1] * v2[1]

particles = []
eps = 1
for line in open('27.txt'):
    x, y, vx, vy, m, p = line.replace(',', '.').split()
    x, y, vx, vy, m, p = float(x), float(y), float(vx), float(vy), float(m), p
    L = m * abs(x * vy - y * vx)
    particles.append((x, y, vx, vy, m, p, L))

clusters = []
while particles:
    clusters.append([particles.pop()])
    for p in clusters[-1]:
        neigh = [part for part in particles if abs(p[6] - part[6]) < eps]
        clusters[-1] += neigh
        for part in neigh:
            particles.remove(part)

#print(len(clusters), [len(cl) for cl in clusters])
centers = []
for cl in clusters:
    c = None
    mdist = float('inf')
    for p in cl:
        d = sum(manh((p[0], p[1]), (pt[0], pt[1])) for pt in cl)
        if d == mdist and c and c[1] < p[1]:
            c = p
        if d < mdist:
            mdist = d
            c = p
    centers.append(c)

Q1 = sum((c[2]**2 + c[3]**2)**0.5 for c in centers)
tmp = []
for cl in clusters:
    p35 = [p for p in cl if p[5] in ('III', 'V')]
    for i in range(len(p35) - 1):
        x1, y1, v1x, v1y, m1, p1, L1 = p35[i]
        for j in range(i + 1, len(p35)):
            x2, y2, v2x, v2y, m2, p2, L2 = p35[j]
            if scal((v1x, v1y), (v2x, v2y)) < 0:
                tmp.append(dist((x1, y1), (x2, y2)))

Q2 = min(tmp)
            
print(int(Q1 * 10_000), int(Q2 * 10_000))