Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #299484
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
Вам даны два входных файла ($А$ и $B$), каждый из которых имеет описанную выше структуру.
В ответе запишите два числа через запятую: сначала максимальное расстояние между центрами кластеров для файла $А$, затем для файла $B$. В качестве значения указывайте целую часть от умножения найденного числового значения на $10,000$.
Центр здесь определяется через минимакс: это точка кластера, у которой наибольшее расстояние до остальных точек кластера минимально (чебышёвский центр среди самих точек). Заодно это значение — радиус кластера, и по нему удобно проверять, что разбиение допустимо: все радиусы должны быть не больше $2$.
Кластеризация. Кластеры — плотные сгустки точек, разделённые пустыми промежутками, поэтому разбиваем точки на компоненты связности с небольшим порогом. Порог $0{,}3$ мал: от групп отрываются одиночки (в файле $А$ две, в файле $B$ семь). Начиная с $0{,}5$ результат стабилен, но в файле $B$ уже при $1{,}5$ две соседние группы сливаются. Рабочий диапазон — от $0{,}5$ до $1{,}0$, берём $0{,}5$.
Дальше всё просто: находим центр каждого кластера и перебираем пары центров, беря максимум расстояния.
Одно замечание про производительность: в файле $B$ почти $10,000$ точек, и поиск центра «в лоб» — это порядка $2000^2 = 4 \cdot 10^6$ операций на кластер, что вполне терпимо. А вот попытка искать центр перебором по всем $10,000$ точкам сразу, без разбиения на кластеры, была бы в $25$ раз дороже и всё равно неверна по смыслу.
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 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 center(c): # минимакс: минимум наибольшего расстояния
return min(c, key=lambda a: max(math.dist(a, b) for b in c))
for name in ['27-21A.ods', '27-21B.ods']:
cen = [center(c) for c in clusters(load(name))]
d = max(math.dist(a, b) for a, b in combinations(cen, 2))
print(int(d * 10000))
Результаты для файла $А$. Всего $1076$ точек, три кластера по $400$, $360$ и $316$ точек с центрами $(5{,}089851;\ -0{,}104547)$, $(-2{,}530080;\ -4{,}287915)$ и $(-2{,}271530;\ 4{,}473791)$ и радиусами $0{,}757589$, $0{,}860867$ и $1{,}029041$ — все меньше $2$, разбиение допустимо. Три попарных расстояния между центрами равны $8{,}695$, $7{,}367$ и $8{,}765520$; наибольшее — между центрами кластеров из $316$ и $360$ точек: $8{,}7655201$. После умножения на $10,000$ и отбрасывания дробной части получаем $87655$.
Результаты для файла $B$. Всего $9943$ точки, пять кластеров: $2052$, $2036$, $2020$, $1945$ и $1890$ точек с центрами $(0{,}967322;\ -2{,}912958)$, $(-2{,}391762;\ 1{,}727137)$, $(0{,}940500;\ 2{,}824079)$, $(3{,}013202;\ -0{,}006159)$ и $(-2{,}289035;\ -1{,}660634)$; радиусы от $0{,}933735$ до $1{,}229973$, все укладываются в $2$. Из десяти попарных расстояний наибольшее $5{,}7370996$ — между центрами кластеров из $2036$ и $1945$ точек, что даёт $57370$.
20
