Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299515
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
Вам даны два входных файла ($А$ и $B$), каждый из которых имеет описанную выше структуру.
В ответе запишите два числа: сначала минимальное расстояние между центрами кластеров для файла $А$, затем для файла $B$. В качестве значения указывайте целую часть от умножения найденного числового значения на $10,000$.
Обратите внимание: центр здесь определяется через суммарное расстояние (минимум суммы), а не через минимакс, как в некоторых других вариантах этой задачи. Ищем его перебором по точкам кластера.
Кластеризация. Кластеры — плотные сгустки точек, разделённые пустыми промежутками, поэтому разбиваем точки на компоненты связности. Порог $0{,}3$ мал: от групп отрываются одиночки (в файле $А$ две, в файле $B$ семь). Начиная с $0{,}5$ результат стабилен, но в файле $B$ уже при $1{,}5$ две соседние группы сливаются, а при $2{,}0$ всё схлопывается в один кластер. Рабочий диапазон — от $0{,}5$ до $1{,}0$, берём $0{,}8$.
Проверка допустимости: радиус каждого кластера (наибольшее удаление его точки от центра) должен быть не больше $2$. В файле $А$ радиусы равны $0{,}9175$, $1{,}1198$ и $0{,}8860$, в файле $B$ — от $0{,}9836$ до $1{,}2375$. Все укладываются, а слитый вариант при пороге $1{,}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) < 2: continue
try: P.append((float(tok[0]), float(tok[1])))
except ValueError: pass
return P
def center(c): # минимум СУММЫ расстояний
return min(c, key=lambda a: sum(math.dist(a, b) for b in c))
def clusters(pts, eps=0.8):
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
for name in ['27-30A.ods', '27-30B.ods']:
cen = [center(c) for c in clusters(load(name))]
d = min(math.dist(a, b) for a, b in combinations(cen, 2))
print(int(d * 10000))
Результаты для файла $А$. Всего $1076$ точек, три кластера по $400$, $360$ и $316$ точек с центрами $(5{,}003999413;\ -0{,}003813954)$, $(-2{,}498032462;\ -4{,}336089529)$ и $(-2{,}505466232;\ 4{,}336246000)$. Три попарных расстояния равны $8{,}663088$, $8{,}671$ и $8{,}672$; минимальное — между центрами кластеров из $400$ и $360$ точек: $8{,}6630880$. После умножения на $10,000$ и отбрасывания дробной части получаем $86630$.
Результаты для файла $B$. Всего $9943$ точки, пять кластеров: $2052$, $2036$, $2020$, $1945$ и $1890$ точек с центрами $(0{,}926109440;\ -2{,}856890703)$, $(-2{,}422434580;\ 1{,}761267787)$, $(0{,}926418659;\ 2{,}853877467)$, $(3{,}001308472;\ -0{,}001073967)$ и $(-2{,}426362681;\ -1{,}762845891)$. Из десяти попарных расстояний наименьшее $3{,}5225863$ — между центрами кластеров из $2036$ и $1890$ точек, что даёт $35225$.
20
