Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298943
В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям.
По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров — кругов радиуса не более $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-14-A.ods', 1.0), ('27-14-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{,}8791;\ 0{,}9956)$, $(1{,}6313;\ 4{,}1401)$ и $(5{,}0790;\ 7{,}0557)$ и радиусами $0{,}847718$, $0{,}832726$ и $1{,}167601$. Все радиусы меньше $3$ — разбиение допустимо. Исключаем самый малочисленный кластер (из $309$ точек, радиус $0{,}847718$) и усредняем оставшиеся: $(0{,}832726 + 1{,}167601) / 2 = 1{,}0001633$, что после умножения на $10,000$ даёт $10001$.
Результаты для файла $B$. Всего $9917$ точек, пять кластеров: $1907$, $1940$, $2011$, $2027$ и $2032$ точки. Их центры — $(0{,}9903;\ 7{,}1282)$, $(-2{,}9906;\ 0{,}9137)$, $(4{,}9732;\ 7{,}0110)$, $(3{,}0064;\ 3{,}9177)$ и $(0{,}8339;\ 3{,}0211)$, радиусы — $1{,}611410$, $1{,}010885$, $0{,}507085$, $1{,}071062$ и $0{,}812671$, все укладываются в $3$. Исключаем кластер из $1907$ точек и усредняем четыре оставшихся радиуса: $(1{,}010885 + 0{,}507085 + 1{,}071062 + 0{,}812671) / 4 = 0{,}8504258$, что даёт $8504$.
20
