Е27.10 Будем называть медианой по х такую точку, что половина(кроме самой точки) точек по значению абсциссы будет больше её абсциссы

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

1 год назад

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

Будем называть медианой по х такую точку, что половина(кроме самой точки) точек по значению абсциссы будет больше её абсциссы, а половина меньше. А медианой по y аналогичное значение в ординатах. Гарантируется единственной такого значения в каждом кластере. Так же гарантируется, что в каждом кластере нечётное количество точек.

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

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

Возможные данные одного из файлов иллюстрированы графиком.

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

ege-inf-zad27-10A.txt

ege-inf-zad27-10B.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-10A.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 medianaX(cl):
    for p in cl:
        k = len([p1 for p1 in cl if p1[0]>p[0]])
        k1 = len([p1 for p1 in cl if p1[0] < p[0]])
        if k==k1:
            return p[0]
def medianaY(cl):
    for p in cl:
        k = len([p1 for p1 in cl if p1[1]>p[1]])
        k1 = len([p1 for p1 in cl if p1[1] < p[1]])
        if k==k1:
            return p[1]

medx = [medianaX(cl) for cl in clusters]
medy = [medianaY(cl) for cl in clusters]
px = sum(medx)/len(medx)
py = sum(medy)/len(medy)
print(int(px*10000), int(py*10000))

from math import dist

from turtle import*

from random import*

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

for p in cl:

k = len([p1 for p1 in cl if p1[0]>p[0]])

k1 = len([p1 for p1 in cl if p1[0] < p[0]])

if k==k1:

return p[0]

def medianaY(cl):

for p in cl:

k = len([p1 for p1 in cl if p1[1]>p[1]])

k1 = len([p1 for p1 in cl if p1[1] < p[1]])

if k==k1:

return p[1]

medx = [medianaX(cl) for cl in clusters]

medy = [medianaY(cl) for cl in clusters]

px = sum(medx)/len(medx)

py = sum(medy)/len(medy)

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

[431, 441]
40893 9686

для файла Б

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

f = open('ege-inf-zad27-10B.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 medianaX(cl):
    for p in cl:
        k = len([p1 for p1 in cl if p1[0]>p[0]])
        k1 = len([p1 for p1 in cl if p1[0] < p[0]])
        if k==k1:
            return p[0]
def medianaY(cl):
    for p in cl:
        k = len([p1 for p1 in cl if p1[1]>p[1]])
        k1 = len([p1 for p1 in cl if p1[1] < p[1]])
        if k==k1:
            return p[1]

medx = [medianaX(cl) for cl in clusters]
medy = [medianaY(cl) for cl in clusters]
px = sum(medx)/len(medx)
py = sum(medy)/len(medy)
print(int(px*10000), int(py*10000))

from math import dist

from turtle import*

from random import*

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

for p in cl:

k = len([p1 for p1 in cl if p1[0]>p[0]])

k1 = len([p1 for p1 in cl if p1[0] < p[0]])

if k==k1:

return p[0]

def medianaY(cl):

for p in cl:

k = len([p1 for p1 in cl if p1[1]>p[1]])

k1 = len([p1 for p1 in cl if p1[1] < p[1]])

if k==k1:

return p[1]

medx = [medianaX(cl) for cl in clusters]

medy = [medianaY(cl) for cl in clusters]

px = sum(medx)/len(medx)

py = sum(medy)/len(medy)

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

[3267, 3289, 3317]
30438 41916

Ответ:

40893 9686
30438 41916