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

Задание 27

Формулировка задачи 95470 КЕГЭ-27

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

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

Цвет:                     Размер:
O — голубой               I    — карлик
B — бело-голубой          II   — субкарлик
A — белый                 III  — гигант
F — жёлто-белый           IV   — сверхгигант
G — жёлтый                V    — мегагигант
K — оранжевый             VI   — супергигант
M — красный

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

Антицентром кластера называется точка кластера, сумма расстояний от которой до всех остальных точек кластера максимальна; для каждого кластера антицентр единственен. Расстояние между точками A(x₁, y₁) и B(x₂, y₂):

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

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

Для файла A определите координаты центра (антицентра) каждого кластера, затем найдите два числа: A₁ — минимальное расстояние от голубого субкарлика до центра его кластера; A₂ — сумму расстояний центров кластеров до точки (−1, 2). Для файла B определите центры кластеров, затем найдите два числа: B₁ — абсциссу центра кластера с минимальным количеством субкарликов; B₂ — ординату центра того же кластера.

В ответе запишите четыре числа: целую часть значения A₁ × 10000, затем целую часть значения A₂ × 10000, затем число B₁ × 10000, затем число B₂ × 10000.

'''
Из-за разных формулировок вопросов для файла A и B задание лучше решать параллельно
Зададим словари со значениями 'A', 'B' - которые будут определять какую из задач решаем.
Этапы задач будем делать параллельно (запуская поочередно для A  и B)
'''
# Чтение данных, определение формата
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'B' # это код задачи, которую решаем
df = [] # список для данных (пока без разбивки на кластеры)
for s in open(fname[kz]):
  df.append(s)
print (kz, len(df), df[:2])

Запустили для A

A 147 ['4.4767 4.4438 F3III\n', '4.2939 21.2005 M7VI\n']
Запустили для B
B 270 ['9.0283 8.3062 G8II\n', '9.1296 28.5816 O7IV\n']
Следующий этап - разбиение данных на абциссу, ординату и кортеж параметров (цвет, яркость, тип звезды)

# Чтение данных, разбиение на параметры
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'B' # это код задачи, которую решаем
df = [] # список для данных (пока без разбивки на кластеры)
for s in open(fname[kz]):
  x, y, z = s.split()
  x, y = float(x), float(y)
  z = (z[0], int(z[1]), z[2:])
  df.append((x,y,z))
print (kz, len(df), df[:2])

Добавили пару строк и запустили для одной из задач (можно и для двух)
B 270 [(9.0283, 8.3062, ('G', 8, 'II')), (9.1296, 28.5816, ('O', 7, 'IV'))]
Теперь неплохо определить область изменения абцисс и ординат.
Так как это временная характеристика, то сделаем это с помощью подпрограммы

def razmah(a):
  x0 = min([xyz[0] for xyz in a])
  x1 = max([xyz[0] for xyz in a])
  y0 = min([xyz[1] for xyz in a])
  y1 = max([xyz[1] for xyz in a])
  return x0,x1,y0,y1
          
# Чтение данных, разбиение на параметры
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'B' # это код задачи, которую решаем
df = [] # список для данных (пока без разбивки на кластеры)
for s in open(fname[kz]):
  x, y, z = s.split()
  x, y = float(x), float(y)
  z = (z[0], int(z[1]), z[2:])
  df.append((x,y,z))
print (kz, razmah(df))

Запустили для A
A (3.7426, 6.2873, 3.3395, 21.6865)
Запустили для B
B (6.7027, 9.2925, 6.309, 29.5998)
В общем случае, желательно нарисовать данные точки с помощью turtle (считаем, что других инструментов нет),
но в данном случае использую данные о размерах кластеров (H=4, W=3) можно сделать выводы:

Для A (два кластера)
- 1-й с ординатоя меньшей 11
- 2-й с ординатой большей 17
Для B (три кластера) - несколько сложнее (учитываем что кластеры хорошо различаются)
- 1-й с ординатой меньше 14
- 3-й с ординатой большей 25
- 2-й все остальное

Теперь разобъм точки на кластеры. Для этого:

Заменим df со списка на словарь df={1:[], 2:[], 3:[]}
Для принадлежности точки кластеру напишем программу dot2claster(x, y, kz) - которая по точке и номеру задания определяет номер кластера
Выведем информацию для каждого кластера (кол-во точек, размеры)

def razmah(a):
  x0 = min([xyz[0] for xyz in a])
  x1 = max([xyz[0] for xyz in a])
  y0 = min([xyz[1] for xyz in a])
  y1 = max([xyz[1] for xyz in a])
  return x0,x1,y0,y1
def dot2claster(x,y,kz):
  if kz == 'A' and y < 11 : return 1
  if kz == 'A' : return 2
  if y < 14 : return 1
  if y > 25 : return 3
  return 2
          
# Чтение данных, разбиение на параметры
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'B' # это код задачи, которую решаем
df = {1:[], 2:[], 3:[]} # словарь кластеров
for s in open(fname[kz]):
  x, y, z = s.split()
  x, y = float(x), float(y)
  z = (z[0], int(z[1]), z[2:])
  j = dot2claster(x,y,kz)
  df[j].append((x,y,z))
# определяем характеристики кластеров
for d in df:
  if df[d] :
    print (kz+str(d), len(df[d]), razmah(df[d]))

Запускаем для 'A'
A1 71 (3.7557, 6.2568, 3.3395, 6.5956)
A2 76 (3.7426, 6.2873, 18.3573, 21.6865)
Запускаем для 'B'
B1 90 (6.7027, 9.2347, 6.309, 9.5736)
B2 90 (6.7135, 9.2704, 16.3448, 19.594)
B3 90 (6.7527, 9.2925, 26.374, 29.5998)
Анализ показывает, что разбиение прошло правильно (особенно важно для B)

Теперь необходимо определить центры кластеров.
Для этого необходимо написать три однострочника

def dist(a,b) - евклидовое расстояние между двум звездами
def srast(dot,a) - сумма расстояний от точки dot до всех точек списка a
def centr(a) - пределение центра/антицентра кластера a (для центра ищем min, для антицентра nax

Добавим эти программы и выведем результаты по кластерам

def razmah(a):
  x0 = min([xyz[0] for xyz in a])
  x1 = max([xyz[0] for xyz in a])
  y0 = min([xyz[1] for xyz in a])
  y1 = max([xyz[1] for xyz in a])
  return x0,x1,y0,y1
def dot2claster(x,y,kz):
  if kz == 'A' and y < 11 : return 1
  if kz == 'A' : return 2
  if y < 14 : return 1
  if y > 25 : return 3
  return 2
def dist (a,b):
  return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
def srast(t, a) :
  return sum([dist(t, dot) for dot in a])
def centr(a):
  return max([(srast(dot,a), dot) for dot in a])

# Чтение данных, разбиение на параметры
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'A' # это код задачи, которую решаем
df = {1:[], 2:[], 3:[]} # словарь кластеров
for s in open(fname[kz]):
  x, y, z = s.split()
  x, y = float(x), float(y)
  z = (z[0], int(z[1]), z[2:])
  j = dot2claster(x,y,kz)
  df[j].append((x,y,z))
# определяем характеристики кластеров
for d in df:
  if df[d] :
    print (kz+str(d), centr(df[d]))

Запустим по A
A1 (147.34177032703937, (4.2239, 3.3737, ('G', 7, 'VI')))
A2 (157.86248040868256, (5.9705, 21.6572, ('K', 3, 'VI')))
Запустим по B
B1 (186.75517800325656, (7.2632, 6.309, ('K', 7, 'I')))
B2 (202.253057071744, (9.0233, 19.5843, ('O', 0, 'V')))
B3 (181.80961808341956, (8.9086, 26.374, ('K', 3, 'II')))
Визуальный анализ показывает, что полученные значение лежат в "углах" кластеров (это соответствует "здравому смыслу")
Далее идет поиск ответов для каждого из файлов. Это можно сделать с помощью процедур, а можно занести в основную часть (мы поступим так)
Вначале внесем результаты в словарь (для удобства) и будем вести обработку

def razmah(a):
  x0 = min([xyz[0] for xyz in a])
  x1 = max([xyz[0] for xyz in a])
  y0 = min([xyz[1] for xyz in a])
  y1 = max([xyz[1] for xyz in a])
  return x0,x1,y0,y1
def dot2claster(x,y,kz):
  if kz == 'A' and y < 11 : return 1
  if kz == 'A' : return 2
  if y < 14 : return 1
  if y > 25 : return 3
  return 2
def dist (a,b):
  return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
def srast(t, a) :
  return sum([dist(t, dot) for dot in a])
def centr(a):
  return max([(srast(dot,a), dot) for dot in a])

# Чтение данных, разбиение на параметры
fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
kz = 'B' # это код задачи, которую решаем
df = {1:[], 2:[], 3:[]} # словарь кластеров
for s in open(fname[kz]):
  x, y, z = s.split()
  x, y = float(x), float(y)
  z = (z[0], int(z[1]), z[2:])
  j = dot2claster(x,y,kz)
  df[j].append((x,y,z))
# определяем характеристики кластеров
rez = {}
for d in df:
  if df[d] :
    rez[d] = centr(df[d])
if kz == 'A' :
  ans2 = dist(rez[1][1],(-1,2)) + dist(rez[2][1],(-1,2))
  ''' dot[2][0] - определяет цвет 'O' - голубой, dot[2][2] - тип звезды 'II' - субкарлик
      находим для каждого из кластеров и берем минимальное
      поскольку кластеров всего 2 это легче делать операторами '''
  ans1_1 = min([dist(rez[1][1], dot) for dot in df[1] if dot[2][0] == 'O' and dot[2][2] == 'II']) 
  ans1_2 = min([dist(rez[2][1], dot) for dot in df[2] if dot[2][0] == 'O' and dot[2][2] == 'II'])
  ans1 = min(ans1_1,ans1_2)
  print (kz, ans1*10000, ans2*10000, ans1_1, ans1_2)  
if kz == 'B' :
  ''' Определяем количества cубкарликов в каждом кластере и выводим как ответ
      нужный вариант выбираем визуально '''
  for d in rez :
    k = len([t for t in df[d] if t[2][2] == 'II'])
    print(k, int(rez[d][1][0]*10000), int(rez[d][1][1]*10000))

Запускаем для A (для контроля выводим полные значения и ans1_1, ans1_2
A 21010.859311318043 262579.931705925 3.3923034799380787 2.1010859311318044

Запускаем для B
14 72632 63090
8 90233 195843
17 89086 263740
Для ответа выбираем 2 строку.

Анализ программы:

Параллельное решение программы удобно, поскольку:
- позволяет обрабатывать данные однотипно на ранних этапах
- позволяет контролировать правильность работы и не возвращаться к повторению этапов,
  если бы программа писалась отдельно для A, а потом модифицировалась для B
Промежуточные запуски и сохранение вывода результатов (желательно в блокноте) для контроля позволяет
прослеживать весь путь написания программы и упрощает тестирование
Получение результатов практически происходит сразу
Возможные проблемы:
- разбиение на кластеры может потребовать визуальный анализ с помощью модуля turtle или использование
  табличного редактора, но это не меняет логики программы
- условия обработки результатов для получения ответов может потребовать написания процедур. Лучше сделать две процедуры (отдельно для каждого файла)

Ниже приведен код программы, выводящий нужные ответы сразу

def razmah(a):
  xx = min([xyz[0] for xyz in a]), max([xyz[0] for xyz in a])
  yy = min([xyz[1] for xyz in a]), max([xyz[1] for xyz in a])
  return xx, yy
def dot2claster(x,y,kz):
  if kz == 'A' and y < 11 : return 1
  if kz == 'A' : return 2
  if y < 14 : return 1
  if y > 25 : return 3
  return 2
def dist (a,b):
  return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
def srast(t, a) :
  return sum([dist(t, dot) for dot in a])
def centr(a):
  return max([(srast(dot,a), dot) for dot in a])
def main(kz):
  # Чтение данных, разбиение на параметры
  fname = {'A' : '27A_95470.txt', 'B' : '27B_95470.txt'}
  df = {1:[], 2:[], 3:[]} # словарь кластеров
  for s in open(fname[kz]):
    x, y, z = s.split()
    x, y, z = float(x), float(y), (z[0], int(z[1]), z[2:])
    j = dot2claster(x,y,kz)
    df[j].append((x,y,z))
  rez = {}
  for d in df:
    if df[d] : rez[d] = centr(df[d])
  if kz == 'A' :
    ans2 = dist(rez[1][1],(-1,2)) + dist(rez[2][1],(-1,2))
    ans1_1 = min([dist(rez[1][1], dot) for dot in df[1] if dot[2][0] == 'O' and dot[2][2] == 'II']) 
    ans1_2 = min([dist(rez[2][1], dot) for dot in df[2] if dot[2][0] == 'O' and dot[2][2] == 'II'])
    ans1 = min(ans1_1,ans1_2)
    print (kz, int(ans1*10000), int(ans2*10000))  
  if kz == 'B' :
    r, k = 1, len([t for t in df[1] if t[2][2] == 'II'])
    k2 = len([t for t in df[2] if t[2][2] == 'II'])
    if k2 < k : r, k = 2, k2
    k3 = len([t for t in df[3] if t[2][2] == 'II'])
    if k3 < k : r, k = 3, k3
    print(kz, int(rez[r][1][0]*10000), int(rez[r][1][1]*10000))
for kz in ['A', 'B']: 
  main(kz)

Attached files
27A_95470.txt
27B_95470.txt

Печать