Е27.8 Манхэттенское расстояние между двумя точками A( x1, y1) и B(x2, y2) вычисляется по формуле

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

1 год назад

Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов на картах планет Информатикус и Алгоритмикус. Район (кластер) – это групп населенных пунктов, которые находятся внутри прямоугольника высотой H и шириной W. Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) – это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками и $B (x_{2}, y_{2})$ вычисляется по формуле:

В файле A хранятся данные о точках двух кластеров. В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000.

В файле Б той же структуры хранятся данные о точках трёх кластеров. Известно, что количество точек не превышает 10 000. Возможные данные одного из файлов иллюстрированы графиком.

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

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

ege-inf-zad27-8A.txt ege-inf-zad27-8A.xlsx

ege-inf-zad27-8B.txt ege-inf-zad27-8B.xlsx

Ответ:

для файла А

Px × 10000

Py × 10000

для файла Б

Px × 10000

Py × 10000

kompege.ru № 18053 (В. Ланская, Р. Ягафаров) – задание №27

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

Решение:

Visualizing DBSCAN Clustering

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

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

для файла А

from turtle import*
from random import*
def dist(p1, p2):
    x1, y1 = p1;
    x2, y2 = p2;
    return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-8A.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 centroid(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return min(m)[1]

cen = [centroid(cl) for cl in clusters]
px = sum(x for x,y in cen)/len(cen)
py = sum(y for x,y in cen)/len(cen)
print(abs(int(px*10000)), abs(int(py*10000)))

from turtle import*

from random import*

def dist(p1, p2):

x1, y1 = p1;

x2, y2 = p2;

return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-8A.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 centroid(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return min(m)[1]

cen = [centroid(cl) for cl in clusters]

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

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

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

[73, 65]
31374 25065

для файла Б

from turtle import*
from random import*
def dist(p1, p2):
    x1, y1 = p1;
    x2, y2 = p2;
    return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-8B.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 centroid(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return min(m)[1]

cen = [centroid(cl) for cl in clusters]
px = sum(x for x,y in cen)/len(cen)
py = sum(y for x,y in cen)/len(cen)
print(abs(int(px*10000)), abs(int(py*10000)))

from turtle import*

from random import*

def dist(p1, p2):

x1, y1 = p1;

x2, y2 = p2;

return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-8B.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 centroid(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return min(m)[1]

cen = [centroid(cl) for cl in clusters]

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

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

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

[2216, 3001, 2216]
31622 49268

Ответ:

31374 25065
31622 49268