Расстояния и пары точек

Как найти, насколько далеко от центра разбросаны точки кластера?

Радиус кластера — расстояние от центра до самой далёкой точки своего кластера. Возьмём кластеры файла example27.txt: small — правый из трёх точек, big — левый из пяти. Функция center_sum — из подтемы 3:

small = [(10, 0), (12, 0), (11, 1)]big = [(0, 0), (0, 2), (1, 1), (2, 0), (2, 2)]c_small, c_big = center_sum(small), center_sum(big) r_small = max(dist(c_small, p) for p in small)r_big = max(dist(c_big, p) for p in big)print(r_small, r_big) far = max(dist(c_small, p) for p in big)print(far)

Радиусы обоих кластеров — √2 ≈ 1,414: от центров (11; 1) и (1; 1) до самых далёких точек — по диагонали клетки. Последнее число — уже не радиус: это расстояние от центра малого кластера до самой далёкой точки чужого, большого кластера — до (0; 0) или (0; 2). Перед каждым расчётом реши два вопроса: от чего до чего считаем и среди каких точек выбираем.

Центр ищут один раз, до цикла. В записи max(dist(center_sum(cluster), p) for p in cluster) поиск центра повторится для каждой точки, и программа, которая работала секунду, будет работать часами.

Как найти наибольшее расстояние между двумя точками кластера?

Перебрать все пары точек кластера — каждую один раз — и запомнить наибольшее расстояние. Это диаметр кластера. Определение, как всегда, сверяй с условием: D = max d(A, B), где A и B — точки одного кластера.

def diameter_of(cluster):    diameter = 0.0    for i in range(len(cluster)):        for j in range(i + 1, len(cluster)):            diameter = max(                diameter,                dist(cluster[i], cluster[j])            )    return diameter

print(diameter_of(small), diameter_of(big))

Внутренний цикл начинается с i + 1: каждая пара проверяется один раз, а точка не сравнивается сама с собой.

Если требуется не только расстояние, но и координаты точек, образующих диаметр, нужно запоминать найденную пару. У левого кластера диаметр 2√2 дают сразу две пары — две диагонали квадрата; поэтому в задачах, где важны концы диаметра, условие гарантирует, что пара единственная.

Диаметр не обязан совпадать с расстоянием от выбранного центра до самой далёкой точки. Если известен центр и его радиус R, то диаметр не больше 2R, но равенство выполняется не всегда. Поэтому автоматически писать diameter = 2 * radius нельзя. У правого кластера радиус √2 ≈ 1,414, а диаметр 2 — меньше, чем 2√2.

Как найти самые далёкие друг от друга точки двух разных кластеров?

Брать по одной точке из каждого кластера и запоминать не только наибольшее расстояние, но и саму пару. Это межкластерный диаметр; в задачах часто что-то считают и по его концам. Запусти функцию по шагам: сначала лучшая пара даёт 12, затем ≈ 12,166.

from math import dist  def farthest_pair(cluster1, cluster2):    best_distance = -1.0    best_pair = None    for point1 in cluster1:        for point2 in cluster2:            d = dist(point1, point2)            if d > best_distance:                best_distance = d                best_pair = (point1, point2)    return best_distance, best_pair  print(farthest_pair([(0, 0), (0, 2)], [(12, 0)]))

None — специальное значение, означающее, что результат пока не установлен. Оба кластера здесь предполагаются непустыми, поэтому пара обязательно будет найдена. Функция возвращает два значения, их раскладывают по именам — и теперь можно вычислить, например, модуль разности абсцисс концов и сумму их ординат:

diameter, pair = farthest_pair(small, big)point1, point2 = pair x_difference = abs(point1[0] - point2[0])y_sum = point1[1] + point2[1]print(diameter, pair, x_difference, y_sum)

Если кластеров три, межкластерных диаметров тоже три — по одному на каждую пару кластеров. Пары номеров перебирают так же, как пары точек, — с i + 1:

clusters = [small, big]total = 0.0for i in range(len(clusters)):    for j in range(i + 1, len(clusters)):        d, pair = farthest_pair(clusters[i], clusters[j])        total += d print(total)

Здесь кластеров два, и сумма состоит из одного диаметра.

Если требуется минимальное расстояние между кластерами, организация похожая, но начальное значение — положительная бесконечность, а сравнение — <.

Расстояние между центрами не заменяет расстояния между крайними или ближайшими точками кластеров. Здесь расстояние между центрами — 10, а межкластерный диаметр ≈ 12,166.

И ещё: когда нужно найти минимальное расстояние между различными точками одного кластера, нельзя включать пару точки с самой собой. Иначе минимум всегда получится нулевым. Для различения записей надёжнее использовать разные индексы. Проверка point1 != point2 исключит также разные записи с одинаковыми координатами.

Как посчитать точки на расстоянии не больше r от центра?

Сначала точно определить, среди каких точек считаем и строгое ли неравенство, — и только потом писать цикл. Подсчёт выглядит так:

count = 0 for point in points:    if dist(center, point) <= r:        count += 1

Фраза «на плоскости» может означать все допустимые точки файла. Фраза «этого кластера» — только точки соответствующего кластера: for point in cluster:. Нельзя менять область перебора по привычке. Слова в условии переводятся буквально:

меньше r

dist(center, point) < r

не больше r

dist(center, point) <= r

больше r

dist(center, point) > r

не меньше r

dist(center, point) >= r

Если центр является одной из перебираемых точек, его расстояние до себя равно нулю. При условии <= r и неотрицательном r он будет посчитан. Это правильно, если условие включает центр. Если требуется считать только остальные точки, его нужно исключить как конкретную запись.

Посчитаем для центра (1; 1) и r = 10 все три варианта:

points = small + bigcenter = (1, 1) print(sum(1 for p in points if dist(center, p) <= 10))print(sum(1 for p in points if dist(center, p) < 10))print(sum(1 for p in big if dist(center, p) <= 10))

Те же точки и окружность на рисунке:

«На плоскости, не больше 10» — 7 точек: к пяти точкам своего кластера добавились (10; 0) и (11; 1). «Меньше 10» — 6: точка (11; 1) на самой окружности выпала. «Этого кластера» — 5.

Как найти ближайшую к центру звезду нужного вида или пару таких звёзд?

Сначала отобрать объекты нужного вида, потом искать среди них — внутри одного кластера; центр при этом ищут по всем точкам кластера. В задачах ЕГЭ-2026 спрашивают, например, координаты ближайшего к центру красного гиганта или расстояние между двумя жёлтыми карликами одного кластера. Найдём белый карлик, ближайший к центру самого большого кластера файла 27-3.txt. Функция read_stars — из подтемы 1, split_stars — из подтемы 4:

clusters = split_stars(read_stars("27-3.txt"))big = max(clusters, key=len)center = center_sum([s[:2] for s in big]) dwarfs = [s for s in big if s[2] == "VII"]nearest = min(dwarfs, key=lambda s: dist(center, s[:2])) print(center, len(dwarfs))print(nearest, dist(center, nearest[:2]))

Центр ищем по координатам s[:2] — по всем звёздам кластера, а не только по белым карликам.

max(clusters, key=len) возвращает сам кластер с наибольшим числом точек, min(dwarfs, key=…) — сам ближайший объект, а не расстояние до него; запись lambda s: … — короткая функция для ключа. Если нужен вид, который определяется буквой и светимостью, отбор пишут через parse_kind.

Пары объектов одного вида внутри одного кластера перебирают по индексам, как пары точек для диаметра. Наименьшее расстояние между двумя разными белыми карликами одного кластера:

best = float("inf") for cluster in clusters:    dw = [s[:2] for s in cluster if s[2] == "VII"]     for i in range(len(dw)):        for j in range(i + 1, len(dw)):            best = min(best, dist(dw[i], dw[j])) print(best)

Пары из разных кластеров сюда не попадают: список dw собирается заново для каждого кластера.

Вернёмся к задаче темы:

«Входной файл 27-4.txt содержит сведения о частицах, зарегистрированных детектором. В каждой строке записаны координаты частицы x и y, проекции её скорости vx и vy, масса m и признак частицы — римское число от I до VII; значения разделены табуляцией. Кинетическая энергия частицы E = m · (vx² + vy²) / 2. Частицы образуют четыре кластера: модуль разности энергий любых двух частиц одного кластера не превышает 2. Центром кластера назовём частицу, для которой сумма модулей разностей её энергии и энергий остальных частиц кластера минимальна. Найдите Q₁ — наибольшее расстояние между двумя частицами одного кластера с признаком II и Q₂ — наибольшую кинетическую энергию центра кластера. В ответе запишите целые части произведений Q₁ · 10 000 и Q₂ · 10 000.»

Все шаги уже разобраны: прочитать частицы (подтема 1), разделить по энергии (подтема 2), найти центры по разности энергий (подтема 3) и посчитать два ответа на одних и тех же кластерах. Q₁ — наибольшее расстояние между частицами с признаком II внутри одного кластера — это пары, как у диаметра, только среди отобранных частиц. Q₂ — наибольшая энергия центра.

from math import dist  def read_particles(filename):    particles = []    with open(filename, encoding="utf-8-sig") as f:        for line in f:            parts = line.replace(",", ".").split()            x, y, vx, vy, m = [float(v) for v in parts[:5]]            particles.append((x, y, vx, vy, m, parts[5]))    return particles  def energy(p):    return p[4] * (p[2] ** 2 + p[3] ** 2) / 2  def energy_gap(a, b):    return abs(energy(a) - energy(b))  def center_sum(cluster, d=dist):    best_point = cluster[0]    best_sum = float("inf")    for candidate in cluster:        total = 0.0        for point in cluster:            total += d(candidate, point)        if total < best_sum:            best_sum = total            best_point = candidate    return best_point  particles = read_particles("27-4.txt")bounds = [3.5, 7, 10.5]groups = [[] for _ in range(len(bounds) + 1)]for p in particles:    groups[sum(energy(p) > b for b in bounds)].append(p) q1 = 0.0for g in groups:    tagged = [p[:2] for p in g if p[5] == "II"]    for i in range(len(tagged)):        for j in range(i + 1, len(tagged)):            q1 = max(q1, dist(tagged[i], tagged[j])) q2 = max(energy(center_sum(g, energy_gap)) for g in groups)print(int(q1 * 10000), int(q2 * 10000))

Ответ: 772010 125026. Новое в программе только одно место — номер группы: это число границ, которые энергия частицы превысила, а sum считает истинные сравнения как единицы. Файл задачи — 27-4.txt.

Q₁ считают по координатам — p[:2], хотя кластеры и центры выбирали по энергии. А список частиц с признаком II собирают заново в каждом кластере: пары из разных кластеров в Q₁ не входят.

• Радиусот центра до самой далёкой точки своего кластера
• Центрищут один раз, до цикла по точкам
• Диаметрпары с j от i + 1; не обязан быть 2R
• Межкластерныйпо точке из двух кластеров; запоминай и пару
• В радиусесреди каких точек и строгое ли неравенство
• Нужный видсначала отбор, потом поиск — внутри кластера