Статья Автор: Лебедев Дмитрий Алексеевич

Задание 27_Пишем программу для 2026

Формулировка задания КЕГЭ 95469 (2026. ДВ)

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор точек на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит ровно одному кластеру.

Истинный центр кластера (центроид) — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается евклидово расстояние между точками A(x₁, y₁) и B(x₂, y₂):

d(A, B) = sqrt( (x1 − x2)^2 + (y1 − y2)^2 )

В файле A хранятся данные о звёздах двух кластеров, где H = 6.5, W = 4.5 для каждого кластера; количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H = 5, W = 4 для каждого кластера; количество звёзд не превышает 10000. В каждой строке файла записана информация об одной звезде: сначала координата x, затем координата y (значения в условных единицах). Структура файла B аналогична файлу A.

Известно, что в каждом файле имеются координаты ровно трёх «лишних» точек, представляющих аномалии (помехи при передаче данных). Эти точки не относятся ни к одному кластеру, их учитывать не нужно.

Для файла A определите координаты центра каждого кластера, затем найдите два числа: P_x — минимальную из абсцисс центров кластеров и P_y — минимальную из ординат центров кластеров. Для файла B определите координаты центра каждого кластера, затем найдите два числа: Q₁ — минимальное расстояние между центрами кластеров и Q₂ — максимальное расстояние между центрами кластеров.

В ответе запишите четыре числа: абсолютную величину целой части произведения P_x × 10000, затем абсолютную величину целой части произведения P_y × 10000, затем абсолютную величину целой части произведения Q₁ × 10000, затем абсолютную величину целой части произведения Q₂ × 10000.

def dot2claster(xy, kz):
  if kz == 'A' and xy[1] < 9 : return 1
  if kz == 'A' : return 2
  if kz == 'B' and xy[0] < 9 :return 1
  if kz == 'B' and xy[0] > 16 :return 3
  return 2
def razmah (a):
  xx = min([xy[0] for xy in a]), max([xy[0] for xy in a])
  yy = min([xy[1] for xy in a]), max([xy[1] for xy in a])
  return xx, yy
def dist(a,b) :
  return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
def srast(dot, a) :
  return sum([dist(dot,t) for t in a])
def center(a):
  return min([(srast(dot,a),dot) for dot in a])
def main(kz):
  fname = {'A' : '27A_95469.txt','B' : '27B_95469.txt'}
  df =[]
  for s in open(fname[kz]) :
    x, y = map(float, s.split())
    df.append((x,y))
  df.sort()
  if kz == 'A' : df = df[1:-2]
  if kz == 'B' : df = df[1:-2]
  dp ={1:[], 2:[], 3:[]}
  for xy in df:
    j =dot2claster(xy,kz)
    dp[j].append(xy)
  rez ={}
  for i in dp:
    if dp[i] :
      rez[i] = center(dp[i])[1]
      print(kz, razmah(dp[i]), rez) 
  if kz == 'A' :
    ans1, ans2  = int(min(rez[1][0],rez[2][0])*10000), int(min(rez[1][1],rez[2][1])*10000)
    print(kz,ans1,ans2)
  if kz == 'B' :
    ans1  = int(min(dist(rez[1],rez[2]),dist(rez[1],rez[3]),dist(rez[3],rez[2]))*10000)
    ans2  = int(max(dist(rez[1],rez[2]),dist(rez[1],rez[3]),dist(rez[3],rez[2]))*10000)
    print(kz,ans1,ans2)
    
              
for kz in ['A','B'] :
  main(kz)

Последовательность решения

Создаем модель решения сразу для двух файлов
def main(kz) :
pass
for kz in ['A','B'] :
main(kz)
все остальное пишем в main или отдельными def
Определяем имя файла, считываем данные в список.
Так как есть три аномальные точки, то сортируем (оказалось, что достаточно простой сортировки)
Выводим первых 5 и последних 5 - видим, что анамольные в начале и конце.
Вырезаем нужный кусок, выводим ограничения (def razmah)
Определяем разбиение на кластеры: для A по ординате, для B по абциссе (левый, правый, остальное)
(def dot2claster) Выводим границы и проверяем визуально
Находим центры кластеров (с помощью def dist, def srast, def center) Выводим границы и центр
Читаем вопросы к файлу A и файлу B. Так как все значения положительные, то игнорируем абсолютное значение целой части
( поскольку для числа -3,5 это 4, а не 3) и выводим ответ.

При решении файл не открывался в табличном редакторе и не строилась диаграмма

Attached files
27A_95469.txt
27B_95469.txt

Печать