Е27.26 Q1 – наибольшее евклидово расстояние между частицами одного кластера

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

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

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

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

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

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

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

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

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

Q₁ — наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II, и
Q₂ — максимальное значение кинетической энергии для центра кластера.

В ответе запишите два числа: сначала целую часть произведения
Q₁ × 10 000,
затем целую часть произведения
Q₂ × 10 000.

Для справки

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

E = 1/2 · m(V_x² + V_y²).

Евклидово расстояние между двумя точками на плоскости
A(x₁, y₁) и
B(x₂, y₂)
вычисляется по формуле:

d(A, B) =
√((x₂ − x₁)² +
(y₂ − y₁)²).

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

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

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

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.txt

Ответ:

Q1 × 10000

Q2 × 10000

Демонстрационный вариант ЕГЭ 2027 по информатике – задание №27

Решение:

Нужно разбить все частицы на 4 кластера по значениям кинетической энергии,
причём для любых двух частиц одного кластера модуль разности их кинетических энергий
не должен превышать R = 2.

После этого для каждого кластера нужно определить его центр, а затем найти:

Q1 — наибольшее евклидово расстояние между частицами одного кластера, имеющими признак II;
Q2 — максимальное значение кинетической энергии центра кластера.

Используем следующий код:

from math import sqrt

R = 2.0
K = 4

data = []

with open('27.txt') as f:
    for line in f:
        x, y, vx, vy, m, t = line.split()

        x = float(x.replace(',', '.'))
        y = float(y.replace(',', '.'))
        vx = float(vx.replace(',', '.'))
        vy = float(vy.replace(',', '.'))
        m = float(m.replace(',', '.'))

        E = m * (vx ** 2 + vy ** 2) / 2

        data.append([E, x, y, t])


# Сортируем частицы по кинетической энергии
data.sort()

clusters = []
start = 0

for i in range(1, len(data)):
    if data[i][0] - data[start][0] > R:
        clusters.append(data[start:i])
        start = i

clusters.append(data[start:])


# Находим центры кластеров
centers = []

for cluster in clusters:
    best = None
    best_sum = float('inf')

    for p in cluster:
        s = 0

        for q in cluster:
            s += abs(p[0] - q[0])

        if s < best_sum:
            best_sum = s
            best = p

    centers.append(best)


# Q1 — максимальное расстояние между частицами
# с признаком II внутри одного кластера
Q1 = 0

for cluster in clusters:
    a = [p for p in cluster if p[3] == 'II']

    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            d = sqrt(
                (a[i][1] - a[j][1]) ** 2 +
                (a[i][2] - a[j][2]) ** 2
            )

            Q1 = max(Q1, d)


# Q2 — максимальная кинетическая энергия центра кластера
Q2 = max(p[0] for p in centers)


print(int(Q1 * 10000), int(Q2 * 10000))

from math import sqrt

R = 2.0

K = 4

data = []

with open('27.txt') as f:

for line in f:

x, y, vx, vy, m, t = line.split()

x = float(x.replace(',', '.'))

y = float(y.replace(',', '.'))

vx = float(vx.replace(',', '.'))

vy = float(vy.replace(',', '.'))

m = float(m.replace(',', '.'))

E = m * (vx ** 2 + vy ** 2) / 2

data.append([E, x, y, t])

# Сортируем частицы по кинетической энергии

data.sort()

clusters = []

start = 0

for i in range(1, len(data)):

if data[i][0] - data[start][0] > R:

clusters.append(data[start:i])

start = i

clusters.append(data[start:])

# Находим центры кластеров

centers = []

for cluster in clusters:

best = None

best_sum = float('inf')

for p in cluster:

s = 0

for q in cluster:

s += abs(p[0] - q[0])

if s < best_sum:

best_sum = s

best = p

centers.append(best)

# Q1 — максимальное расстояние между частицами

# с признаком II внутри одного кластера

Q1 = 0

for cluster in clusters:

a = [p for p in cluster if p[3] == 'II']

for i in range(len(a)):

for j in range(i + 1, len(a)):

d = sqrt(

(a[i][1] - a[j][1]) ** 2 +

(a[i][2] - a[j][2]) ** 2

)

Q1 = max(Q1, d)

# Q2 — максимальная кинетическая энергия центра кластера

Q2 = max(p[0] for p in centers)

print(int(Q1 * 10000), int(Q2 * 10000))

Разбор программы

Сначала подключаем функцию sqrt() для вычисления квадратного корня:

from math import sqrt

1	from math import sqrt

Задаём значение R = 2 и количество кластеров:

R = 2.0
K = 4

1 2	R = 2.0 K = 4

Затем считываем данные о каждой частице:

with open('27.txt') as f:
    for line in f:
        x, y, vx, vy, m, t = line.split()

with open('27.txt') as f:

for line in f:

x, y, vx, vy, m, t = line.split()

В каждой строке файла находятся:
координаты x и y,
проекции скорости vx и vy,
масса m и признак t.

Так как вещественные числа в файле записаны через запятую,
заменяем запятую на точку и преобразуем значения в тип float:

x = float(x.replace(',', '.'))
y = float(y.replace(',', '.'))
vx = float(vx.replace(',', '.'))
vy = float(vy.replace(',', '.'))
m = float(m.replace(',', '.'))

x = float(x.replace(',', '.'))

y = float(y.replace(',', '.'))

vx = float(vx.replace(',', '.'))

vy = float(vy.replace(',', '.'))

m = float(m.replace(',', '.'))

Вычисление кинетической энергии

Кинетическая энергия вычисляется по формуле:

E = 1/2 · m · (vx² + vy²)

В программе:

E = m * (vx ** 2 + vy ** 2) / 2

1	E = m * (vx 2 + vy 2) / 2

Для каждой частицы сохраняем её энергию, координаты и признак:

data.append([E, x, y, t])

1	data.append([E, x, y, t])

Разбиение на кластеры

Сначала сортируем все частицы по кинетической энергии:

data.sort()

1	data.sort()

После сортировки частицы идут в порядке возрастания энергии.
Для каждого кластера сравниваем энергию текущей частицы
с энергией первой частицы этого кластера:

if data[i][0] - data[start][0] > R:

1	if data[i][0] - data[start][0] > R:

Если разность становится больше 2,
то текущий кластер заканчивается и начинается новый:

clusters.append(data[start:i])
start = i

1 2	clusters.append(data[start:i]) start = i

Последний кластер добавляем после завершения цикла:

clusters.append(data[start:])

1	clusters.append(data[start:])

Поиск центра кластера

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

Для каждой частицы p вычисляем эту сумму:

s = 0

for q in cluster:
    s += abs(p[0] - q[0])

s = 0

for q in cluster:

s += abs(p[0] - q[0])

Здесь p[0] и q[0] — кинетические энергии двух частиц.

Если полученная сумма меньше ранее найденной,
сохраняем эту частицу как лучший кандидат на центр:

if s < best_sum:
    best_sum = s
    best = p

if s < best_sum:

best_sum = s

best = p

После перебора всех частиц сохраняем найденный центр:

centers.append(best)

1	centers.append(best)

Вычисление Q1

Для каждого кластера выбираем только частицы с признаком II:

a = [p for p in cluster if p[3] == 'II']

1	a = [p for p in cluster if p[3] == 'II']

После этого перебираем все пары таких частиц:

for i in range(len(a)):
    for j in range(i + 1, len(a)):

1 2	for i in range(len(a)): for j in range(i + 1, len(a)):

Для каждой пары вычисляем евклидово расстояние:

d = sqrt(
    (a[i][1] - a[j][1]) ** 2 +
    (a[i][2] - a[j][2]) ** 2
)

d = sqrt(

(a[i][1] - a[j][1]) ** 2 +

(a[i][2] - a[j][2]) ** 2

)

Это соответствует формуле:

d = √((x2 - x1)² + (y2 - y1)²)

Сохраняем максимальное найденное расстояние:

Q1 = max(Q1, d)

1	Q1 = max(Q1, d)

Вычисление Q2

В списке centers уже находятся центры всех кластеров.
Кинетическая энергия каждой частицы хранится в элементе с индексом 0.

Поэтому максимальную энергию центра кластера находим так:

Q2 = max(p[0] for p in centers)

1	Q2 = max(p[0] for p in centers)

Формирование ответа

По условию требуется умножить значения Q1 и Q2
на 10000 и взять целую часть:

print(int(Q1 * 10000), int(Q2 * 10000))

1	print(int(Q1 * 10000), int(Q2 * 10000))

Идея решения

Сначала для каждой частицы вычисляется кинетическая энергия.
Затем частицы сортируются по энергии и разбиваются на 4 кластера так,
чтобы разность максимальной и минимальной энергии внутри одного кластера
не превышала 2.
После этого в каждом кластере находится его центр.
Далее вычисляется максимальное расстояние между частицами с признаком II
внутри одного кластера и максимальная кинетическая энергия среди центров кластеров.

Ответ:

539936 100704