Карточки
Тесты
Главная
Курсы
Подписка
27. Программирование: #298968
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $N$ непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной $H$ и $W$, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В ответе запишите четыре числа через запятую: сначала $P_1$, затем $P_2$; сначала целую часть произведения $Q_1 \times 10,000$, затем целую часть произведения $Q_2 \times 10,000$.
Возможные данные одного из файлов иллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.
Центр здесь определяется через сумму расстояний (а не через минимакс, как в «лабораторных» задачах) — это точка самого кластера, ищем её перебором.
Кластеризация. Прямоугольники не пересекаются, поэтому кластеры разделены в пространстве. Разбиваем точки на компоненты связности, но порог нужен заметно больше обычного: точек мало ($207$ и $473$), сгустки разрежены, и при пороге $0{,}8$ файл $А$ рассыпается на четыре куска. Устойчивый результат в файле $А$ начинается с $1{,}5$, в файле $Б$ он один и тот же при любом пороге от $0{,}5$ до $2$. Проверяем: число кластеров совпадает с условием, и каждый укладывается в прямоугольник заданного размера — например, кластеры файла $Б$ занимают около $3{,}4$ по $x$ и $3{,}7$ по $y$ при допустимых $5$ и $5$.
Отдельно про формулировку $P_1$ и $P_2$: сказано «точек на плоскости», а не «точек кластера», то есть считать надо все точки файла. Для $P_1$ это ничего не меняет (в круге радиуса $0{,}7$ лежат только свои), а для $P_2$ разница существенная: далёкий второй кластер целиком попадает в «не менее $1{,}3$».
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 center(c):
return min(c, key=lambda a: sum(math.dist(a, b) for b in c))
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
A = load('27-17_A.ods')
ca = clusters(A, 1.5)
cb, cs = center(max(ca, key=len)), center(min(ca, key=len))
P1 = sum(math.dist(p, cb) <= 0.7 for p in A)
P2 = sum(math.dist(p, cs) >= 1.3 for p in A)
print(P1, P2)
B = load('27-17_B.ods')
q = (1.7, 2.3)
d = [math.dist(center(c), q) for c in clusters(B, 1.0)]
print(int(min(d) * 10000), int(max(d) * 10000))
Результаты для файла $А$. Всего $207$ точек, кластеры содержат $112$ и $95$ точек. Больший занимает область $x \in [69{,}30;\ 75{,}17]$, $y \in [23{,}13;\ 27{,}17]$, его центр — $(72{,}650608;\ 25{,}162900)$; меньший занимает $x \in [82{,}42;\ 88{,}14]$, $y \in [52{,}98;\ 57{,}03]$ с центром $(85{,}288101;\ 55{,}033462)$.
В круг радиуса $0{,}7$ вокруг центра большего кластера попадают $5$ точек вместе с самим центром, значит, $P_1 = 5$.
На расстоянии не менее $1{,}3$ от центра меньшего кластера лежат $183$ точки: $71$ из самого этого кластера и все $112$ точек соседнего, который целиком удалён более чем на $30$ единиц. Отсюда $P_2 = 183$. Если понимать формулировку иначе — считать только точки того же кластера, — получилось бы $71$; на мой взгляд, слова «точек на плоскости» указывают именно на все точки файла.
Результаты для файла $Б$. Всего $473$ точки, три кластера по $166$, $157$ и $150$ точек с центрами $(14{,}775198;\ 37{,}051204)$, $(13{,}883750;\ 30{,}908588)$ и $(15{,}382013;\ 24{,}565478)$. Точка $(1{,}7;\ 2{,}3)$ лежит далеко в стороне, расстояния до центров равны $37{,}129597$, $31{,}094937$ и $26{,}133293$. Значит, $Q_1 = 26{,}133293$ и $Q_2 = 37{,}129597$, что после умножения на $10,000$ и отбрасывания дробной части даёт $261332$ и $371295$.
20
