Е27.11 Будем называть диагональю кластера такой отрезок, что образующие его две точки кластера максимально отдалены друг от друга

Администратор

1 год назад

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть диагональю кластера такой отрезок, что образующие его две точки кластера максимально отдалены друг от друга. Гарантируется единственной такой пары точек в кластере. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для каждого файла определите координаты точек образующих диагональ каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс образующих диагонали точек кластеров, и Py – среднее арифметическое ординат образующих диагонали точек кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10000, затем целую часть произведения Py×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

ege-inf-zad27-11A.txt

ege-inf-zad27-11B.txt

Ответ:

для файла А

Px × 10000

Py × 10000

для файла Б

Px × 10000

Py × 10000

kompege.ru № 20207 (В. Лашин) – задание №27

Показать решение...

Решение:

Visualizing DBSCAN Clustering

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

Решение: Кабанов Алексей

для файла А

from math import dist
from turtle import*
from random import*

f = open('ege-inf-zad27-11A.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.replace(',','.').split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 1]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()
def diagonal(cl):
    m = []
    for p in cl:
        for p1 in cl:
            m.append([dist(p, p1), [p, p1]])
    return max(m)[1]

dia = [p for cl in clusters for p in diagonal(cl)]
px = sum(x for x,y in dia)/len(dia)
py = sum(y for x,y in dia)/len(dia)
print(int(px*10000), int(py*10000))

from math import dist

from turtle import*

from random import*

f = open('ege-inf-zad27-11A.txt')

data = []

for s in f:

x,y = [float(d) for d in s.replace(',','.').split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 1]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def diagonal(cl):

m = []

for p in cl:

for p1 in cl:

m.append([dist(p, p1), [p, p1]])

return max(m)[1]

dia = [p for cl in clusters for p in diagonal(cl)]

px = sum(x for x,y in dia)/len(dia)

py = sum(y for x,y in dia)/len(dia)

print(int(px*10000), int(py*10000))

[75, 50]
16730 48696

для файла Б

from math import dist
from turtle import*
from random import*

f = open('ege-inf-zad27-11B.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.replace(',','.').split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 1]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()
def diagonal(cl):
    m = []
    for p in cl:
        for p1 in cl:
            m.append([dist(p, p1), [p, p1]])
    return max(m)[1]

dia = [p for cl in clusters for p in diagonal(cl)]
px = sum(x for x,y in dia)/len(dia)
py = sum(y for x,y in dia)/len(dia)
print(int(px*10000), int(py*10000))

from math import dist

from turtle import*

from random import*

f = open('ege-inf-zad27-11B.txt')

data = []

for s in f:

x,y = [float(d) for d in s.replace(',','.').split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 1]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def diagonal(cl):

m = []

for p in cl:

for p1 in cl:

m.append([dist(p, p1), [p, p1]])

return max(m)[1]

dia = [p for cl in clusters for p in diagonal(cl)]

px = sum(x for x,y in dia)/len(dia)

py = sum(y for x,y in dia)/len(dia)

print(int(px*10000), int(py*10000))

[2964, 3002, 2959]
23982 47539

Ответ:

16730 48696
23982 47539