Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298950
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — кругов радиуса не более $3$ единиц так, что каждая точка попадает ровно в один кластер.
Вам даны два входных файла ($А$ и $B$), каждый из которых имеет описанную выше структуру. По данным каждого из представленных файлов определите средний радиус по описанным выше правилам.
В ответе запишите два числа через запятую: сначала средний радиус для файла $А$, затем для файла $B$. В качестве значения указывайте целую часть от умножения найденного числового значения на $10000$.
Определение центра здесь не такое, как в «звёздных» задачах: минимизируется не сумма расстояний, а максимальное расстояние до остальных точек кластера. Это чебышёвский центр, выбранный среди самих точек, и вместе с ним сразу получается радиус — то самое минимальное максимальное расстояние. Считается всё одним двойным перебором: для каждой точки кластера находим её удаление от самой далёкой точки кластера, затем берём наименьшее из этих значений.
Кластеризация. Кластеры — плотные сгустки точек, разделённые пустыми промежутками, поэтому разбиваем точки на компоненты связности с небольшим порогом. Дальше обязательно проверяем результат: все найденные кластеры должны укладываться в круг радиуса не более $3$.
С порогом надо быть аккуратным в обе стороны. В файле $А$ порог $0{,}5$ мал — от кластеров отрывается одиночная точка; начиная с $1{,}0$ получаются три устойчивые группы. В файле $B$ наоборот: уже при пороге $1{,}0$ две соседние группы сливаются, поэтому берём $0{,}5$ и получаем пять групп. Что групп действительно пять, видно по зазорам: у самой близкой пары групп минимальное расстояние между точками разных кластеров равно $0{,}84$, у остальных больше, тогда как внутри каждой группы точки идут вплотную.
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):
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, eps in [('27-15-A.ods', 1.0), ('27-15-B.ods', 0.5)]:
cl = sorted(clusters(load(name), eps), key=len)
r = [radius(c) for c in cl[:-1]] # самый многочисленный кластер исключаем
print(int(sum(r) / len(r) * 10000))
Результаты для файла $А$. Всего $942$ точки, три кластера по $309$, $314$ и $319$ точек с радиусами $0{,}847718$, $0{,}832726$ и $1{,}167601$. Все радиусы меньше $3$ — разбиение допустимо. Исключаем самый многочисленный кластер (из $319$ точек, радиус $1{,}167601$) и усредняем оставшиеся: $(0{,}847718 + 0{,}832726) / 2 = 0{,}8402222$, что после умножения на $10,000$ даёт $8402$.
Результаты для файла $B$. Всего $9917$ точек, пять кластеров: $1907$, $1940$, $2011$, $2027$ и $2032$ точки с радиусами $1{,}611410$, $1{,}010885$, $0{,}507085$, $1{,}071062$ и $0{,}812671$; все укладываются в $3$. Исключаем кластер из $2032$ точек (радиус $0{,}812671$) и усредняем четыре оставшихся: $(1{,}611410 + 1{,}010885 + 0{,}507085 + 1{,}071062) / 4 = 1{,}0501104$, что даёт $10501$.
Обратите внимание, насколько разными получаются ответы при исключении наибольшего и наименьшего кластера: в файле $B$ размеры кластеров близки ($1907$ против $2032$), и перепутать их легко, а результат меняется с $8504$ на $10501$.
20
