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

Определение центра здесь не такое, как в «звёздных» задачах: минимизируется не сумма расстояний, а максимальное расстояние до остальных точек кластера. Это чебышёвский центр, выбранный среди самих точек, и вместе с ним сразу получается радиус — то самое минимальное максимальное расстояние. Считается всё одним двойным перебором: для каждой точки кластера находим её удаление от самой далёкой точки кластера, затем берём наименьшее из этих значений.

Кластеризация. Кластеры — плотные сгустки точек, разделённые пустыми промежутками, поэтому разбиваем точки на компоненты связности с небольшим порогом. Дальше обязательно проверяем результат: все найденные кластеры должны укладываться в круг радиуса не более $3$.

Порог здесь критичен в обе стороны. При $0{,}3$ от кластеров отрываются одиночные точки — в файле $А$ таких обрывков четыре, в файле $B$ три. При $1{,}0$ и больше в файле $B$ две соседние группы сливаются, и вместо пяти кластеров остаётся четыре. Устойчивый диапазон — от $0{,}5$ до $0{,}8$, его и берём. Что групп в файле $B$ действительно пять, подтверждают зазоры: у самой близкой пары групп минимальное расстояние между точками разных кластеров равно $0{,}84$, у остальных пар — от $1{,}56$ и больше, тогда как внутри каждой группы точки идут вплотную.

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

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) < 2: continue
        try: P.append((float(tok[0]), float(tok[1])))
        except ValueError: pass
    return P

def clusters(pts, eps=0.5):
    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], pts[j]) < eps:
                    unused.discard(j); comp.append(j); stack.append(j)
        res.append([pts[k] for k in comp])
    return res

def radius(c):                            # центр — минимакс, радиус — его максимум
    return min(max(math.dist(a, b) for b in c) for a in c)

for name in ['27-13_A.ods', '27-13_B.ods']:
    cl = sorted(clusters(load(name)), key=len)
    r = [radius(c) for c in cl[:-1]]      # самый многочисленный кластер исключаем
    print(int(sum(r) / len(r) * 10000))

Результаты для файла $А$. Всего $880$ точек, три кластера по $285$, $291$ и $304$ точки с центрами $(1{,}9020;\ 3{,}9863)$, $(-1{,}0156;\ 1{,}0238)$ и $(4{,}9314;\ 6{,}9158)$ и радиусами $0{,}783859$, $0{,}977617$ и $1{,}019754$. Все радиусы меньше $3$ — разбиение допустимо. Исключаем самый многочисленный кластер (из $304$ точек, радиус $1{,}019754$) и усредняем оставшиеся: $(0{,}783859 + 0{,}977617) / 2 = 0{,}8807380$, что после умножения на $10,000$ даёт $8807$.

Результаты для файла $B$. Всего $9927$ точек, пять кластеров: $1937$, $1972$, $1987$, $2011$ и $2020$ точек. Их центры — $(0{,}9597;\ 7{,}0404)$, $(5{,}0743;\ 7{,}0380)$, $(3{,}0335;\ 3{,}9589)$, $(-3{,}0818;\ 0{,}9859)$ и $(0{,}7991;\ 3{,}0539)$, радиусы — $1{,}450878$, $0{,}692539$, $1{,}011702$, $1{,}141591$ и $0{,}901021$, все укладываются в $3$. Исключаем кластер из $2020$ точек (радиус $0{,}901021$) и усредняем четыре оставшихся: $(1{,}450878 + 0{,}692539 + 1{,}011702 + 1{,}141591) / 4 = 1{,}0741776$, что даёт $10741$.

Обратите внимание, насколько близки размеры кластеров в файле $B$: от $1937$ до $2020$ точек. Ошибка в разбиении на единицы точек здесь может изменить то, какой кластер считается наибольшим, и испортить ответ — поэтому и важно, что при порогах от $0{,}5$ до $0{,}8$ результат не меняется.