27. Программирование: #298924

Сначала расшифруем обозначения по двум таблицам. Бело-голубой яркий гигант — спектральный класс $B$ и светимость $II$. Жёлтый карлик — класс $G$ и светимость $V$. Оранжевый карлик — класс $K$ и светимость $V$. Классы $V$, $VI$ и $VII$ легко перепутать: $K2V$ — карлик, $K2VI$ — субкарлик, а $VII$ записан вообще без буквы.

Разбор строки. Первые два поля — координаты, третье либо равно $VII$, либо устроено как «буква, цифра, римское число». Значит, спектральный класс — первый символ, класс светимости — всё начиная с третьего (второй символ — подкласс, он нигде не нужен). Белые карлики обрабатываем отдельно: спектрального класса у них нет.

Отдельная сложность этих файлов — разнобой в десятичных разделителях: часть чисел записана с точкой и распознана таблицей как число, часть с запятой и осталась текстом, из-за чего некоторые строки склеены в одну ячейку. Поэтому надёжнее собрать текст всей строки, заменить запятые на точки и разделить по пробелам — тогда в любом случае получаются три поля. Именно так работает функция load ниже, читающая .ods напрямую.

Кластеризация. Прямоугольники не пересекаются, поэтому кластеры разделены в пространстве, и достаточно разбить точки на компоненты связности: объединяем точки, отстоящие друг от друга меньше чем на порог. Здесь подходит порог $1{,}0$: при пороге $1{,}5$ два кластера файла $Б$ сливаются в один и вместо трёх получаются два. Проверка простая: количество найденных кластеров должно совпасть с указанным в условии, а каждый кластер — уместиться в прямоугольник $6{,}0 \times 5{,}5$.

Центр кластера — точка самого кластера с минимальной суммой расстояний до остальных, ищем перебором. Считать среднее арифметическое координат нельзя.

import zipfile, math
from xml.etree import ElementTree as ET
from itertools import combinations

T = '{urn:oasis:names:tc:opendocument:xmlns:table:1.0}'
O = '{urn:oasis:names:tc:opendocument:xmlns:office:1.0}'

def load(name):
    x = ET.fromstring(zipfile.ZipFile(name).read('content.xml'))
    P = []
    for r in x.iter(T + 'table-row'):
        parts = []
        for c in r.iter(T + 'table-cell'):
            v = c.get(O + 'value') or ''.join(c.itertext()).strip()
            if v: parts.append(v)
        tok = ' '.join(parts).replace(',', '.').split()   # чиним разнобой форматов
        if len(tok) < 3: continue
        s = tok[2]
        sp, lum = (None, 'VII') if s == 'VII' else (s[0], s[2:])
        P.append((float(tok[0]), float(tok[1]), sp, lum))
    return P

def center(c):
    return min(c, key=lambda a: sum(math.dist(a[:2], b[:2]) for b in c))

def clusters(pts, eps=1.0):
    unused, res = set(range(len(pts))), []
    while unused:
        i = unused.pop(); comp, stack = [i], [i]
        while stack:
            a = stack.pop()
            for j in list(unused):
                if math.dist(pts[a][:2], pts[j][:2]) < eps:
                    unused.discard(j); comp.append(j); stack.append(j)
        res.append([pts[k] for k in comp])
    return res

A = load('27-10_A.ods')
big = max(clusters(A), key=len)                  # самый многочисленный кластер
cn = center(big)
bb = [p for p in big if p[2] == 'B' and p[3] == 'II']
best = min(bb, key=lambda p: math.dist(p[:2], cn[:2]))
print(int(abs(best[0] * 10000)), int(abs(best[1] * 10000)))

B = load('27-10_B.ods')
cl = sorted(clusters(B), key=lambda c: sum(p[2] == 'G' and p[3] == 'V' for p in c))
B1 = math.dist(center(cl[0])[:2], center(cl[-1])[:2])
B2 = max(math.dist(u[:2], v[:2])
         for c in cl
         for u, v in combinations([p for p in c if p[2] == 'K' and p[3] == 'V'], 2))
print(int(B1 * 10000), int(B2 * 10000))

Результаты для файла $А$. Всего $406$ звёзд, кластеры содержат $189$ и $217$ точек. Больший занимает область $x \in [5{,}17;\ 9{,}72]$, $y \in [18{,}00;\ 21{,}78]$ и укладывается в прямоугольник $6{,}0 \times 5{,}5$. Его центр — звезда $K3III$ с координатами $(7{,}809724;\ 19{,}825386)$. Бело-голубых ярких гигантов ($B$, $II$) в этом кластере три; ближайший к центру удалён на $0{,}6126$ и имеет координаты $(8{,}405798;\ 19{,}684129)$. Отсюда $A_x = 8{,}405798$ и $A_y = 19{,}684129$, что после умножения на $10,000$ и отбрасывания дробной части даёт $84057$ и $196841$.

Результаты для файла $Б$. Всего $1851$ звезда, кластеры содержат $1170$, $393$ и $288$ точек с центрами $(11{,}734736;\ 24{,}990912)$, $(13{,}218446;\ 36{,}584488)$ и $(18{,}7851;\ 36{,}95248)$. Жёлтых карликов ($G$, $V$) в них $25$, $8$ и $11$: меньше всего в кластере из $393$ точек, больше всего в кластере из $1170$ точек. Расстояние между их центрами $B_1 = 11{,}6881307$.

Оранжевых карликов ($K$, $V$) в кластерах $24$, $10$ и $2$; перебирая пары внутри каждого кластера, получаем наибольшее расстояние $B_2 = 3{,}891464$. Умножаем на $10,000$ и берём целые части: $116881$ и $38914$.