27.01 Стандартные кластеры - Каталог заданий по ЕГЭ

Ошибка.
Попробуйте повторить позже

Задача 1#99576Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах четырёх кластеров, где $R = 2$ . Известно, что количество звёзд не превышает 11268. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $Px ⋅250$ для файла А и $Py ⋅250$ для файла А, далее целую часть произведения $Px ⋅300$ для файла Б и $Py ⋅300$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Нанесём на график две прямые: $y = x$ и $y = − x$ :

$PIC$

Точки, находящиеся в пересечении неравенств:

$y ≥ x$

$y ≥ − x$

принадлежат верхнему(первому) кластеру.

Точки, находящиеся в пересечении неравенств:

$y ≥ x$

$y ≤ − x$

принадлежат левому(второму) кластеру.

Точки, находящиеся в пересечении неравенств:

$y ≤ x$

$y ≥ − x$

принадлежат правому(третьему) кластеру.

Код программы для файла А:

f = open(’27_2_A.txt’)
n = f.readline()
clusters = [[] for i in range(3)]
for i in range(4119):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if y >= x and y >= -x:
        clusters[0].append(star)
    elif y >= x and y <= - x:
        clusters[1].append(star)
    elif y <= x and y >= -x:
        clusters[2].append(star)

sum_x = sum_y = tx = ty = 0
for i in clusters:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 250))
print(int(sum_y / len(clusters) * 250))

Диаграмма для файла Б имеет вид:

$PIC$

Нанесём на график две прямые: $y = 0.5x$ и $y = − 0.5x$ :

$PIC$

Теперь мы можем разделить кластеры. Точки, которые удовлетворяют пересечению неравенств:

$y ≥ 0,5x$

$y ≥ − 0,5x$

принадлежат верхнему(первому) кластеру.

Точки, которые удовлетворяют пересечению неравенств:

$y ≥ 0,5x$

$y ≤ − 0,5x$

принадлежат правому(второму) кластеру.

Точки, которые удовлетворяют пересечению неравенств:

$y ≤ 0,5x$

$y ≤ − 0,5x$

принадлежат нижнему(третьему) кластеру.

Точки, которые удовлетворяют пересечению неравенств:

$y ≥ 0,5x$

$y ≤ − 0,5x$

принадлежат левому(четвертому) кластеру.

Код программы для файла Б:

f = open(’27_2_B.txt’)
n = f.readline()
clusters = [[] for i in range(4)]
for i in range(11268):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if y >= 0.5*x and y >= -0.5*x:
        clusters[0].append(star)
    elif y >= 0.5*x and y <= -0.5*x:
        clusters[1].append(star)
    elif y <= 0.5*x and y >= -0.5*x:
        clusters[2].append(star)
    elif y <= 0.5*x and y <= -0.5*x:
        clusters[3].append(star)

sum_x = sum_y = tx = ty = 0
for i in clusters:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 300))
print(int(sum_y / len(clusters) * 300))

Ответ: -9 402 -19 -93

Ошибка.
Попробуйте повторить позже

Задача 2#99577Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

В файле A хранятся данные о звёздах двух кластеров, где $R = 4$ у верхнего кластера и $R = 5$ у нижнего кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество звёзд не превышает 3215.

В файле Б хранятся данные о звёздах трёх кластеров, где $R = 3$ у левого кластера, $R = 4$ у верхнего кластера и $R = 5$ у правого кластера. Известно, что количество звёзд не превышает 15682. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $Px ⋅250$ для файла А и $Py ⋅250$ для файла А, далее целую часть произведения $Px ⋅300$ для файла Б и $Py ⋅300$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Нанесём на график прямую: $y = 8 + x$ :

$PIC$

Точки, которые удовлетворяют неравенству: $y ≥ 8+ x$ принадлежат верхнему(первому) кластеру. Все остальные - нижнему(второму) кластеру.

Код программы для файла А:

f = open(’27_3_A.txt’)
n = f.readline()
clusters = [[] for i in range(2)]
for i in range(3215):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x,y = star[0],star[1]
    if y >= 8 + x:
        clusters[0].append(star)
    else:
        clusters[1].append(star)

sum_x = sum_y = 0
for i in clusters:
    tx = ty = 0
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 250))
print(int(sum_y / len(clusters) * 250))

Диаграмма для файла Б имеет вид:

$PIC$

Нанесём на график две прямые: $y = 7+ x$ и $y = − 6− x$ :

$PIC$

Теперь можем провести определить какие звезды к каким кластерам относятся.

Если точка находится в пересечении неравенств: $y ≥ 7+ x$ и $y ≥ − 6− x$ , то данная точка относится к верхнему (первому) кластеру.

Если точка находится в пересечении неравенств: $y ≥ 7+ x$ и $y ≤ − 6− x$ , то данная точка относится к левому (второму) кластеру.

Если точка находится в пересечении неравенств: $y ≤ 7+ x$ и $y ≥ − 6− x$ , то данная точка относится к правому (третьему) кластеру.

Код программы для файла Б:

f = open(’27_3_B.txt’)
n = f.readline()
clusters = [[] for i in range(3)]
for i in range(15682):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    x, y = star[0], star[1]
    if y >= 7 + x and y >= -6 - x:
        clusters[0].append(star)
    elif y >= 7 + x and y <= -6 - x:
        clusters[1].append(star)
    elif y <= 7 + x and y >= -6 - x:
        clusters[2].append(star)

sum_x = sum_y = 0
for i in clusters:
    tx = ty = 0
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / len(clusters) * 300))
print(int(sum_y / len(clusters) * 300))

Ответ: -635 1231 -1619 979

Ошибка.
Попробуйте повторить позже

Задача 3#100940Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B (x2,y2)$ на плоскости, которое вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть $Px ⋅10$ для файла А, затем $Py ⋅10$ для файла А, далее целую часть $Px ⋅10$ для файла Б и $Py ⋅10$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Из нее видно, что все точки, чьи абсциссы больше 0, принадлежат одному кластеру, а абсциссы меньше 0 – другому.

Код программы для файла А:

f = open(’1A.txt’)
n = f.readline()
a = [[] for i in range(2)]
for i in range(999):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] > 0:
        a[0].append(star)
    else:
        a[1].append(star)
sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / 2 * 10))
print(int(sum_y / 2 * 10))

Диаграмма для файла Б имеет вид:

$PIC$

Из нее видно, что все точки, чьи ординаты больше 0, принадлежать первому кластеру; точки, чьи ординаты находятся в интервале (-30; 0) – второму кластеру; остальные точки – третьему.

Код программы для файла Б:

f = open(’1B.txt’)
n = f.readline()
a = [[] for i in range(3)]
for i in range(9998):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[1] > 0:
        a[0].append(star)
    elif star[1] > -30 and star[1] < 0:
        a[1].append(star)
    else:
        a[2].append(star)
sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(sum_x / 3 * 10))
print(int(sum_y / 3 * 10))

Ответ: -108 -374 -101 -183

Ошибка.
Попробуйте повторить позже

Задача 4#101102Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B (x2,y2)$ на плоскости, которое вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

В файле Б хранятся данные о звёздах четырех кластеров, где $R = 7$ для каждого кластера. Известно, что количество звёзд не превышает 15000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть $|Px|⋅10$ для файла А, затем $|Py|⋅10$ для файла А, далее целую часть $|Px |⋅10$ для файла Б и $|Py|⋅10$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Из нее видно, что все точки, чьи ординаты больше -5, принадлежат одному кластеру; если ординаты находятся в пределах от -20 до -5, то точки принадлежат второму кластеру, иначе – третьему.

Код программы для файла А:

f = open(’2A.txt’)
n = f.readline()
a = [[] for i in range(3)]
for i in range(1799):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if star[1] > -5:
        a[0].append(star)
    elif star[1] > -20:
        a[1].append(star)
    else:
        a[2].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 3) * 10))
print(int(abs(sum_y / 3) * 10))

Диаграмма для файла Б имеет вид:

$PIC$

Из нее видно, что все точки, чьи абсциссы больше 0, принадлежат первому кластеру; иначе точки с абсциссами, которые быольше -52 – второму кластеру; точки, чьи ординаты больше 20 – третьему кластеру; остальные точки – четвертому.

Код программы для файла Б:

f = open(’2B.txt’)
n = f.readline()
a = [[] for i in range(4)]
for i in range(14999):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] > 0:
        a[0].append(star)
    elif star[0] > -52:
        a[1].append(star)
    elif star[1] > 20:
        a[2].append(star)
    else:
        a[3].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 4) * 10))
print(int(abs(sum_y / 4) * 10))

Ответ: 297 169 368 256

Ошибка.
Попробуйте повторить позже

Задача 5#101107Максимум баллов за задание: 2

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

Истинная периферия кластера, или перифероид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

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

Для каждого файла определите координаты периферии каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс периферий кластеров, и $Py$ – среднее арифметическое ординат периферий кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $|Px|⋅100$ для файла А, затем $|Py|⋅100$ для файла А, далее целую часть произведения $|Px|⋅100$ для файла Б и $|Py|⋅100$ для файла Б.

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

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

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Рассмотрим интервалы, в которых лежит каждый кластер:

1)x > 0

2)x < 0

Код программы для файла А:

f = open(’5A.txt’)
n = f.readline()
a = [[] for i in range(2)]
for i in range(1199):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] > 0:
        a[0].append(star)
    else:
        a[1].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mx = -100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 2) * 100))
print(int(abs(sum_y / 2) * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим интервалы, в которых лежит каждый кластер:

1)x > 0,y < 0

2)x > 0,y > 0

3)x < 0,y < 0

Код программы для файла Б:

f = open(’5B.txt’)
n = f.readline()
a = [[] for i in range(3)]
for i in range(13997):
    star = list(map(float, f.readline().replace(’,’, ’.’).split()))
    if (star[0] > 0) and (star[1] < 0):
        a[0].append(star)
    elif (star[0] > 0) and (star[1] > 0):
        a[1].append(star)
    else:
        a[2].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mx = -100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 3) * 100))
print(int(abs(sum_y / 3) * 100))

Ответ: 86 171 154 248

Ошибка.
Попробуйте повторить позже

Задача 6#101595Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B (x2,y2)$ на плоскости, которое вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

В файле Б хранятся данные о звёздах шести кластеров, где $R = 7.9$ для каждого кластера. Известно, что количество звёзд не превышает 12000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть $|Px|⋅1000$ для файла А, затем $|Py|⋅1000$ для файла А, далее целую часть $|Px |⋅1000$ для файла Б и $|Py|⋅1000$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Рассмотрим все 10 кластеров и координаты, в которых они находятся:

1) $x < 0,y > 0$

2) $20 < x < 30,60 < y < 70$

3) $15 < x < 25,30 < y < 45$

4) $0 < x < 10,20 < y < 35$

5) $25 < x < 35,− 10 < y < 5$

6) $55 < x < 65,− 35 < y < − 20$

7) $40 < x < 50,− 35 < y < − 25$

8) $30 < x < 40,− 50 < y < − 40$

9) $70 < x < 80,− 60 < y < − 45$

10) $x < 0,y < 0$

Код программы для файла А:

f = open(’1A.txt’)
n = f.readline()
a = [[] for i in range(10)]
for i in range(1999):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] < 0 and star[1] > 0:
        a[0].append(star)
    elif star[0] < 0 and star[1] < 0:
        a[1].append(star)
    elif 20 < star[0] < 30 and 60 < star[1] < 70:
        a[2].append(star)
    elif 15 < star[0] < 25 and 30 < star[1] < 45:
        a[3].append(star)
    elif 0 < star[0] < 10 and 20 < star[1] < 35:
        a[4].append(star)
    elif 25 < star[0] < 35 and -10 < star[1] < 5:
        a[5].append(star)
    elif 55 < star[0] < 65 and -35 < star[1] < -20:
        a[6].append(star)
    elif 40 < star[0] < 50 and -35 < star[1] < -25:
        a[7].append(star)
    elif 30 < star[0] < 40 and -50 < star[1] < -40:
        a[8].append(star)
    elif 70 < star[0] < 80 and -60 < star[1] < -45:
        a[9].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 10) * 1000))
print(int(abs(sum_y / 10) * 1000))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим все 6 кластеров и координаты, в которых они находятся:

1) $x < 0,y > 0$

2) $10 < x < 40,70 < y < 110$

3) $130 < x < 160,70 < y < 110$

4) $100 < x < 130,20 < y < 60$

5) $80 < x < 110,− 30 < y < 10$

6) $40 < x < 70,− 140 < y < − 110$

Код программы для файла Б:

f = open(’1B.txt’)
n = f.readline()
a = [[] for i in range(6)]
for i in range(11999):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] < 0 and star[1] > 0:
        a[0].append(star)
    elif 10 < star[0] < 40 and 70 < star[1] < 110:
        a[1].append(star)
    elif 130 < star[0] < 160 and 70 < star[1] < 110:
        a[2].append(star)
    elif 100 < star[0] < 130 and 20 < star[1] < 60:
        a[3].append(star)
    elif 80 < star[0] < 110 and -30 < star[1] < 10:
        a[4].append(star)
    elif 40 < star[0] < 70 and -140 < star[1] < -110:
        a[5].append(star)

sum_x = sum_y = tx = ty = 0
for i in a:
    mn = 100000050000
    for j in i:
        x1, y1 = j
        sm = 0
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 6) * 1000))
print(int(abs(sum_y / 6) * 1000))

Ответ: 16858 1927 58553 35992

Ошибка.
Попробуйте повторить позже

Задача 7#103235Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров. Истинная периферия кластера, или перифероид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна. Под расстоянием понимается расстояние Евклида между двумя точками $A(x1,y1)$ и $B (x2,y2)$ на плоскости, которое вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

В файле Б хранятся данные о звёздах четырех кластеров, где $R = 3$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты периферии каждого кластера, затем вычислите два числа: $Px$ – произведение абсцисс периферий кластеров, и $Py$ – произведение ординат периферий кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть $|Px|∕100$ для файла А, затем $|Py|∕100$ для файла А, далее целую часть $|Px |∕100$ для файла Б и $|Py|∕100$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Первый кластер находится в отрицательной области абсцисс, а второй – в положительной.

Код программы для файла А:

f = open(’1A.txt’)
n = f.readline()  # Считываем первую строку файла с названиями столбцов
a = [[] for i in range(2)]  # Создаём список для кластеров
# Считваем звёзды и определяем их к кластерам
for i in range(800):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] < 0:
        a[0].append(star)
    else:
        a[1].append(star)

mul_x = mul_y = 1  # Переменные для произведения
for i in a:
    tx = ty = 0  # Координаты текущей периферии кластера
    mx = -100000050000  # Максимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    mul_x *= tx
    mul_y *= ty
print(int(abs(mul_x) / 100))
print(int(abs(mul_y) / 100))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим все 4 кластера и координаты, в которых они находятся:

1) $x > 0$

2) $x < 0,y > 0$

3) $x < − 35$

4) все остальные

Код программы для файла Б:

f = open(’1B.txt’)
n = f.readline()  # Считываем первую строку файла с названиями столбцов
a = [[] for i in range(4)]  # Создаём список для кластеров
# Считваем звёзды и определяем их к кластерам
for i in range(10000):
    star = list(map(float, f.readline().replace(’,’,’.’).split()))
    if star[0] > 0:
        a[0].append(star)
    elif (star[0] < 0) and (star[1] > 0):
        a[1].append(star)
    elif star[0] < -35:
        a[2].append(star)
    else:
        a[3].append(star)

mul_x = mul_y = 1  # Переменные для произведения
for i in a:
    tx = ty = 0  # Координаты текущей периферии кластера
    mx = -100000050000  # Максимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    mul_x *= tx
    mul_y *= ty
print(int(abs(mul_x) / 100))
print(int(abs(mul_y) / 100))

Ответ: 38 7 7106 41705

Ошибка.
Попробуйте повторить позже

Задача 8#103238Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах трёх кластеров, где $R = 8$ . Известно, что количество звёзд не превышает 15000. Структура хранения информации о звездах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — произведение абсцисс центров кластеров, и $Py$ – произведение ординат центров кластеров.

В ответе запишите два числа через пробел: сначала целую часть произведения $Px ⋅Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅Py ⋅1000 000000$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Проведем между ними прямую, разделяющую их. Прямая проходит через две точки: $(− 2,4),(− 4;1)$

Уравнение прямой по двум точкам имеет вид:

-x+-2- = y−-4- − 4+ 2 1− 4

2y − 3x = 14

Соответственно, точки, которые удовлетворяют неравенству

y < 1.5⋅x +7

принадлежат правому кластеру, а остальные – левому

Код программы для файла А:

f = open(’4A.txt’)
n = f.readline()  # Считываем первую строку файла с названиями столбцов
a = [[] for i in range(2)]  # Создаём список для кластеров
for line in f:  # Считваем звёзды и определяем их к кластерам
    x, y = list(map(float, line.replace(’,’, ’.’).split()))
    if y < 1.5 * x + 7:
        a[0].append([x, y])
    else:
        a[1].append([x, y])

mul_x = mul_y = 1  # Переменные для произведения абсцисс и ординат центров
for i in a:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    mul_x *= tx
    mul_y *= ty
print(int(mul_x * mul_y * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Проведем между ними прямые, разделяющие их.

Первая прямая проходит через две точки: $(1.8;0.2),(2.6;1.2)$

Уравнение прямой по двум точкам имеет вид:

x− 1.8 y− 0.2 --------= -------- 2.6− 1.8 1.2− 0.2

x− 1.8 = 0.8y− 0.16

y = 1.25x− 2.05

Соответственно, точки, которые удовлетворяют неравенству

y < 1.25x− 2.05

принадлежат правому кластеру.

Вторая прямая проходит через две точки: $(1.2;0.4),(0.2;1.2)$

Уравнение прямой по двум точкам имеет вид:

x− 1.2 y− 0.4 --------= -------- 0.2− 1.2 1.2− 0.4

0.8x − 0.96 = 0.4− y

y = − 0.8x+ 1.36

Соответственно, точки, которые удовлетворяют неравенству

y < − 0.8 ⋅x+ 1.36

принадлежат левому кластеру.

Остальные точки принадлежат кластеру по центру.

Код программы для файла Б:

f = open(’4B.txt’)
n = f.readline()  # Считываем первую строку файла с названиями столбцов
a = [[] for i in range(3)]  # Создаём список для кластеров
for line in f:  # Считваем звёзды и определяем их к кластерам
    x, y = list(map(float, line.replace(’,’, ’.’).split()))
    if y < 1.25 * x - 2.05:
        a[0].append([x, y])
    elif y < -0.8 * x + 1.36:
        a[1].append([x, y])
    else:
        a[2].append([x, y])

mul_x = mul_y = 1  # Переменные для произведения абсцисс и ординат центров
for i in a:
    tx = ty = 0  # Координаты текущего центра кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    mul_x *= tx
    mul_y *= ty
print(int(mul_y * mul_x * 1_000_000_000))

Ответ: 2505 220

Ошибка.
Попробуйте повторить позже

Задача 9#103462Максимум баллов за задание: 2

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

Истинная периферия кластера, или перифероид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера максимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах двух кластеров, где $H = 5$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты периферии каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс периферий кластеров, и $Py$ – среднее арифметическое ординат периферий кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $|Px|⋅100$ и $|Py|⋅100$ для файла А, далее целую часть произведения $|Px|⋅1000$ и $|Py|⋅1000$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Из нее видно, что все точки, чьи абсциссы меньше -2, принадлежат первому кластеру, далее все точки, чьи ординаты меньше 0 – второму кластеру, а все оставшиеся – третьему кластеру.

Код программы для файла А:

file = open("1_A.txt")
file.readline()
clusters = [[] for i in range(3)]
for star in file:
    x, y = list(map(float, star.replace(’,’, ’.’).split()))
    if x < -2:
        clusters[0].append((x, y))
    elif y < 0:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mx = -10**20
    for periferoid in cluster:
        x1, y1 = periferoid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 3) * 100))
print(int(abs(sum_y / 3) * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Из нее видно, что все точки, чьи ординаты больше -2, принадлежат первому кластеру, а все остальные точки – второму кластеру.

Код программы для файла Б:

file = open("1_B.txt")
file.readline()
clusters = [[] for i in range(2)]
for star in file:
    x, y = list(map(float, star.replace(’,’, ’.’).split()))
    if y > -2:
        clusters[0].append((x, y))
    else:
        clusters[1].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mx = -10**20
    for periferoid in cluster:
        x1, y1 = periferoid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm > mx:
            mx = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 2) * 1000))
print(int(abs(sum_y / 2) * 1000))

Ответ: 92 57 2197 643

Ошибка.
Попробуйте повторить позже

Задача 10#103466Максимум баллов за задание: 2

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра.

Расстояние между двумя точками на плоскости $A(x1,y1)$ и $B (x2,y2)$ вычисляется по формуле:

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

В файле А хранятся координаты точек пяти кластеров, где $H = 3$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$ , затем координата $y$ . Известно, что количество точек не превышает 2000.

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ – среднее арифметическое абсцисс центров кластеров и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $|Px|× 1000$ , затем целую часть произведения $|Py|× 1000$ для файла А, а затем - аналогичные данные для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Для этих 5 кластеров необходимо провести 2 наклонных прямых, чтобы их отделить:

$y = 3.5 +0.5∗ x$ и $y = 4.5 − x$

В итоге получим следующие неравенства для последовательного отделения:

1) $y > 3.5 + 0.5 ∗x$ и $x < − 1.5$

2) $y < 3.5 + 0.5 ∗x$ и $x < − 1.5$

3) $x > 3.5$ и $y < 0.5$

4) $y > 4.5 − x$

5) все остальные точки

Код программы для файла А:

file = open("5_A.txt")
file.readline()
clusters = [[] for i in range(5)]
for star in file:
    x, y = list(map(float, star.replace(’,’, ’.’).split()))
    if (y > 3.5 + 0.5*x) and (x < -1.5):
        clusters[0].append((x, y))
    elif (y < 3.5 + 0.5*x) and (x < -1.5):
        clusters[1].append((x, y))
    elif (x > 3.5) and (y < 0.5):
        clusters[2].append((x, y))
    elif y > 4.5 - x:
        clusters[3].append((x, y))
    else:
        clusters[4].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 5) * 1000))
print(int(abs(sum_y / 5) * 1000))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим 3 кластера и координаты, которыми их можно последовательно отделить:

1) $y > 2∗ x+ 4$

2) $y > − 0.5∗ x− 1$

3) все остальные точки

Код программы для файла Б:

file = open("5_B.txt")
file.readline()
clusters = [[] for i in range(3)]
for star in file:
    x, y = list(map(float, star.replace(’,’, ’.’).split()))
    if y > 2*x + 4:
        clusters[0].append((x, y))
    elif y > -0.5*x - 1:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty

print(int(abs(sum_x / 3) * 1000))
print(int(abs(sum_y / 3) * 1000))

Ответ: 462 711 169 660

Ошибка.
Попробуйте повторить позже

Задача 11#103833Максимум баллов за задание: 2

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри круга радиусом $R$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

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

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс центров кластеров, и $Py$ – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведения $|Px|⋅100$ для файла А и $|Py|⋅100$ для файла А, далее целую часть произведения $|Px|⋅100$ для файла Б и $|Py|⋅100$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Для решения задачи будем использовать метод dbscan. Определим границы для поиска стартовых точек в программе, так как нам необходимо найти лишь одну точку, которая принадлежит каждому кластеру, то границы обозначим примерные. Для первого кластера: $x ∈ [− 10;0],y ∈ [10;20]$ . Для второго кластера: $x ∈ [0;10],y ∈ [0;10]$ . Для третьего кластера: $x ∈ [− 15;− 5],y ∈ [− 15;− 5]$ .

Код программы для файла А:

from math import *
f = open(’2_A.txt’)
s = f.readline() # Считываем первую строку файла с названиями столбцов
# сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# подбираем по 1 звезде для каждого кластера меняя параметры
# for i in range(len(st)):
#     if -15 < st[i][0] < -5 and -15 < st[i][1] < 5:
#         print(i)
#         break

a = [[[st[2][0], st[2][1]]], [[st[0][0], st[0][1]]], [[st[1][0], st[1][1]]]]

st.pop(2), st.pop(1), st.pop(0)

# разделяем звезды на кластеры методом dbscan
for k in range(3):
    for j in a[k]:
        for i in range(len(st)):
            if st[i] != ’*’:
                p = [st[i][0], st[i][1]]
                if dist(p, j) < 1:
                    a[k].append(p)
                    st[i] = ’*’

sum_x = sum_y = 0  # Переменные для суммы абсцисс и ординат периферий
for i in a:
    tx = ty = 0  # Координаты текущей периферии кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 3) * 100))
print(int(abs(sum_y / 3) * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Для решения задачи будем использовать метод dbscan. Определим границы для поиска стартовых точек в программе, так как нам необходимо найти лишь одну точку, которая принадлежит каждому кластеру, то границы обозначим примерные. Для первого кластера: $x ∈ [− 30;− 20],y ∈ [5;15]$ . Для второго кластера: $x ∈ [− 20;− 10],y ∈ [− 20;− 10]$ . Для третьего кластера: $x ∈ [− 10;0],y ∈ [− 10;0]$ . Для четвертого кластера: $x ∈ [0;10],y ∈ [10;20]$ . Для пятого кластера: $x ∈ [10;20],y ∈ [20;30]$ . Для шестого кластера: $x ∈ [15;25],y ∈ [− 5;5]$ .

Код программы для файла Б:

from math import *
f = open(’2_B.txt’)
s = f.readline() # Считываем первую строку файла с названиями столбцов
# сохраняем массив данных
st = [list(map(float, i.replace(’,’, ’.’).split())) for i in f]
# подбираем по 1 звезде для каждого кластера меняя параметры
# for i in range(len(st)):
#     if 15 < st[i][0] < 25 and -5 < st[i][1] < 5:
#         print(i)
#         break

a = [[[st[0][0], st[0][1]]], [[st[7][0], st[7][1]]], [[st[11][0], st[11][1]]], [[st[18][0], st[18][1]]], [[st[4][0], st[4][1]]], [[st[14][0], st[14][1]]]]

st.pop(18), st.pop(14), st.pop(11), st.pop(7), st.pop(4), st.pop(0)

# разделяем звезды на кластеры методом dbscan
for k in range(6):
    for j in a[k]:
        for i in range(len(st)):
            if st[i] != ’*’:
                p = [st[i][0], st[i][1]]
                if dist(p, j) < 1:
                    a[k].append(p)
                    st[i] = ’*’

sum_x = sum_y = tx = ty = 0  # Переменные для суммы абсцисс и ординат периферий
for i in a:
    # tx = ty = 0  # Координаты текущей периферии кластера
    mn = 100000050000  # Минимальное расстояние
    for j in i:
        x1, y1 = j
        sm = 0  # Суммарное расстояние
        for k in i:
            x2, y2 = k
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
print(int(abs(sum_x / 6) * 100))
print(int(abs(sum_y / 6) * 100))

Ответ: 239 204 124 485

Ошибка.
Попробуйте повторить позже

Задача 12#104755Максимум баллов за задание: 2

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

Истинный антицентр кластера, или антицентроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах пяти кластеров, где $H = 5$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты антицентроида каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс антицентров кластеров, и $Py$ – среднее арифметическое ординат антицентров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Px ⋅100$ и $Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅1000$ и $Py ⋅1000$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Для данных 3 кластеров проведём 1 прямую для их отделения:

$y = 2.5 ⋅x − 70$

В итоге получим следующие неравенства для отделения:

1) $2.5⋅x − 70 > y$

2) $y > 20$

3) все остальные точки

Код программы для файла А:

file = open("1A.txt")
file.readline()
clusters = [[] for i in range(3)]
for star in file:
    x, y = list(map(float, star.replace(",", ".").split()))
    if 2.5*x - 70 > y:
        clusters[0].append((x, y))
    elif y > 20:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty

print(int(sum_x / 3 * 100))
print(int(sum_y / 3 * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим 5 кластеров и координаты, которыми их можно последовательно отделить:

1) $x < − 8$

2) $x < 6$

Для 3 кластера проведём прямую через точки $(26,30)$ и $(6,0)$ . Уравнение этой прямой будет $y = 1.5 ⋅x− 9$ . Тогда 3, 4 и 5 кластеры отделятся следующими неравенствами:

3) $1.5⋅x − 9 < y$

4) $y < 8$

5) все остальные точки

Код программы для файла Б:

file = open("1B.txt")
file.readline()
clusters = [[] for i in range(5)]
for star in file:
    x, y = list(map(float, star.replace(",", ".").split()))
    if x < -8:
        clusters[0].append((x, y))
    elif x < 6:
        clusters[1].append((x, y))
    elif 1.5*x - 9 < y:
        clusters[2].append((x, y))
    elif y < 8:
        clusters[3].append((x, y))
    else:
        clusters[4].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1

    sum_x += tx
    sum_y += ty

print(int(sum_x / 5 * 1000))
print(int(sum_y / 5 * 1000))

Ответ: 3266 1691 8542 14729

Ошибка.
Попробуйте повторить позже

Задача 13#104756Максимум баллов за задание: 2

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

Истинный центр антикластера, или антицентроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах трёх кластеров, где $H = 4$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты антицента каждого кластера, затем вычислите два числа: $Px$ — среднее арифметическое абсцисс антицентров кластеров, и $Py$ – среднее арифметическое ординат антицентров кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Px ⋅100$ и $Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅1000$ и $Py ⋅1000$ для файла Б.

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

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

$PIC$

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Рассмотрим 5 кластеров и координаты, которыми их можно последовательно отделить. Для 1 кластера проведём прямую через точки $(0,25)$ и $(− 10,0)$ . Уравнение этой прямой будет $y = 2.5 ⋅x+ 25$ .

1) $2.5⋅x + 25 < y$

2) $x < 3$

3) $y > 18$

4) $y > 7$

5) все остальные точки

Код программы для файла А:

file = open("2A.txt")
file.readline()
clusters = [[] for i in range(5)]
for star in file:
    x, y = list(map(float, star.replace(",", ".").split()))
    if 2.5 * x + 25 < y:
        clusters[0].append((x, y))
    elif x < 3:
        clusters[1].append((x, y))
    elif y > 18:
        clusters[2].append((x, y))
    elif y > 7:
        clusters[3].append((x, y))
    else:
        clusters[4].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1

    sum_x += tx
    sum_y += ty

print(int(sum_x / 5 * 100))
print(int(sum_y / 5 * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Для данных 3 кластеров проведём 1 прямую для их отделения:

$y = − 2.5⋅x+ 20$

В итоге получим следующие неравенства для отделения:

1) $− 2.5 ⋅x+ 20 < y$

2) $y < 5$

3) все остальные точки

Код программы для файла Б:

file = open("2B.txt")
file.readline()
clusters = [[] for i in range(3)]
for star in file:
    x, y = list(map(float, star.replace(",", ".").split()))
    if -2.5 * x + 20 < y:
        clusters[0].append((x, y))
    elif y < 5:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))

sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10**20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2-x1)**2 + (y2-y1)**2)**0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1

    sum_x += tx
    sum_y += ty

print(int(sum_x / 3 * 1000))
print(int(sum_y / 3 * 1000))

Ответ: 665 1153 2795 8742

Ошибка.
Попробуйте повторить позже

Задача 14#104780Максимум баллов за задание: 2

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

Истинная периферия кластера, или перифероид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

d(A, B) = ∘ (x-−-x-)2 +-(y-−-y-)2 2 1 2 1

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

В файле Б хранятся данные о звёздах четырех кластеров, где $H = 5$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты периферии каждого кластера, затем вычислите два числа: $Px$ – среднее арифметическое абсцисс периферий кластеров, и $Py$ – среднее арифметическое ординат периферий кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Px ⋅100$ и $Py ⋅100$ для файла А, далее целую часть произведения $Px ⋅100$ и $Py ⋅100$ для файла Б.

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

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

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Код программы для файла А:

file = open("1_A.txt")
clusters = [[] for _ in range(3)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if -6 * x + 120 < y:
        clusters[0].append((x, y))
    elif y < 15:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Код программы для файла Б:

file = open("1_B.txt")
clusters = [[] for _ in range(4)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if (25 / 12) * x - 25 > y:
        clusters[0].append((x, y))
    elif y > 23:
        clusters[1].append((x, y))
    elif x < 14:
        clusters[2].append((x, y))
    else:
        clusters[3].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Ответ: 1240 1838 1351 1791

Ошибка.
Попробуйте повторить позже

Задача 15#104781Максимум баллов за задание: 2

Учёный-астроном решил провести кластеризацию множества звёзд по их расположению на карте галактики. Кластер – это набор звёзд (точек) на графике, лежащий внутри квадрата со стороной длиной $H$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.

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

∘ -------------------- d(A, B) = (x2 − x1)2 + (y2 − y1)2

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

В файле Б хранятся данные о звёздах трех кластеров, где $H = 6$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты центроида каждого кластера, затем вычислите два числа: $Cx$ – среднее арифметическое абсцисс центроидов кластеров, и $Cy$ – среднее арифметическое ординат центроидов кластеров.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Cx ⋅100$ и $Cy ⋅100$ для файла А, далее целую часть произведения $Cx ⋅100$ и $Cy ⋅100$ для файла Б.

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

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Код программы для файла А:

file = open("2_A.txt")
clusters = [[] for _ in range(5)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if (11 / 9) * x - 77 / 9 > y and y < 11:
        clusters[0].append((x, y))
    elif (11 / 9) * x - 77 / 9 > y:
        clusters[1].append((x, y))
    elif y < 15:
        clusters[2].append((x, y))
    elif x < 10:
        clusters[3].append((x, y))
    else:
        clusters[4].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Код программы для файла Б:

file = open("2_B.txt")
clusters = [[] for _ in range(3)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if x - 10 > y:
        clusters[0].append((x, y))
    elif y > 20:
        clusters[1].append((x, y))
    else:
        clusters[2].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Ответ: 1629 1603 2014 1518

Ошибка.
Попробуйте повторить позже

Задача 16#104782Максимум баллов за задание: 2

Лосяш, увлечённый астрономией, решил исследовать звёздное небо и провести кластеризацию звёзд по их расположению на карте. Каждая звезда представлена точкой на графике, а кластер звёзд – это набор точек, лежащих внутри квадрата со стороной длиной $H$ . Каждая звезда обязательно принадлежит только одному из кластеров.

Центр звёздного скопления – это одна из звёзд, сумма расстояний от которой до всех остальных звёзд в кластере минимальна. Лосяш считает, что эта звезда является ключевой для понимания структуры скопления.

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

d(A, B) = ∘ (x2 −-x1)2 +-(y2 −-y1)2

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

В файле Б хранятся данные о пяти кластерах звёзд, где $H = 6$ для каждого кластера. Известно, что количество звёзд не превышает 10000. Структура хранения информации о звёздах в файле Б аналогична файлу А.

Для каждого файла определите координаты центра звёздного скопления каждого кластера, затем вычислите два числа: $Zx$ – среднее арифметическое абсцисс центров звёздных скоплений, и $Zy$ – среднее арифметическое ординат центров звёздных скоплений.

В ответе запишите четыре числа через пробел: сначала целую часть произведений $Z ⋅100 x$ и $Z ⋅100 y$ для файла А, далее целую часть произведения $Zx ⋅100$ и $Zy ⋅100$ для файла Б.

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

Вложения к задаче

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

Для начала визуально оценим данные в условии кластеры. Для этого откроем предложенные файлы в $Excel$ , перейдем в раздел «Вставка $→$ Диаграммы $→$ Точечная».

Диаграмма для файла А имеет вид:

$PIC$

Рассмотрим 6 кластеров и координаты, которыми их можно последовательно отделить. Верхние 3 кластера от нижних отделим прямой, проходящей через точки $(5,10)$ и $(30,22)$ . Уравнение этой прямой будет $y = 0.48⋅x +7.6$ . Верхние 3 кластера между собой разделим по значениям $x$ и $y$ :

1) $y > 13$

2) $x > 20$

3) $x < 15$

Для нижних 3 кластеров используем:

4) $x > 20$

5) $x < 7$

6) все остальные точки

Код программы для файла А:

file = open("3_A.txt")
clusters = [[] for _ in range(6)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if 0.48 * x + 7.6 > y and y > 13:
        clusters[0].append((x, y))
    elif 0.48 * x + 7.6 > y and x > 20:
        clusters[1].append((x, y))
    elif 0.48 * x + 7.6 > y and x < 15:
        clusters[2].append((x, y))
    elif x > 20:
        clusters[3].append((x, y))
    elif x < 7:
        clusters[4].append((x, y))
    else:
        clusters[5].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Диаграмма для файла Б имеет вид:

$PIC$

Рассмотрим 5 кластеров и координаты, которыми их можно последовательно отделить. Для удобства разделим прямыми кластеры на группы: два левых, два средних, самый правый.

Самый правый кластер можно отделить прямой проходящей через точки $(20;20)$ и $(34;0)$ . Уравнение этой прямой будет $y = (− 10∕7)∗ x+ 340∕7$ .

Два средних кластера можно отделить от остальных с помощью предыдущей прямой и прямой, проходящей через точки $(10;0)$ и $(19;24)$ . Уравнение этой прямой будет $y = (8∕3)∗ x− 80∕3$ . Между собой кластеры группы отделим по координатам $y < 8$ и $y > 9$ .

Оставшиеся два кластера отделим по условиям:

1) $y < 15$

2) все остальные точки

Код программы для файла Б:

file = open("3_B.txt")
clusters = [[] for _ in range(5)]
for star in file:
    x, y = list(map(float, star.strip().split()))
    if (-10 / 7) * x + 340 / 7 < y:
        clusters[0].append((x, y))
    elif (-10 / 7) * x + 340 / 7 > y and (8 / 3) * x - 80 / 3 > y and y < 8:
        clusters[1].append((x, y))
    elif (-10 / 7) * x + 340 / 7 > y and (8 / 3) * x - 80 / 3 > y and y > 9:
        clusters[2].append((x, y))
    elif y < 15:
        clusters[3].append((x, y))
    else:
        clusters[4].append((x, y))
sum_x = sum_y = 0
for cluster in clusters:
    tx = ty = 0
    mn = 10 ** 20
    for centroid in cluster:
        x1, y1 = centroid
        sm = 0
        for star in cluster:
            x2, y2 = star
            sm += ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
        if sm < mn:
            mn = sm
            tx, ty = x1, y1
    sum_x += tx
    sum_y += ty
P_x = sum_x / len(clusters)
P_y = sum_y / len(clusters)
print(int(P_x * 100), int(P_y * 100))

Ответ: 1619 1401 1736 1225