Задание №6530. Архив, необходимый для выполнения задания: ссылка для скачивания. Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: $$ d(A, B) = \sqrt{(x_2 - x_1)^2+(y_2 - y_1)^2}. $$ В файле A хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000. В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно. Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px – минимальную из абсцисс центров кластеров и Py – минимальную из ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 – расстояние между центрами кластеров с минимальным и максимальным количеством точек и Q2 – максимальное расстояние от центра кластера до точки этого же кластера среди всех кластеров. Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000. Возможные данные одного из файлов проиллюстрированы графиком. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.

Задание №6530.
Создание собственной программы. ЕГЭ по информатике

Архив, необходимый для выполнения задания: ссылка для скачивания.

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле: $$ d(A, B) = \sqrt{(x_2 - x_1)^2+(y_2 - y_1)^2}. $$ В файле A хранятся координаты точек двух кластеров, где H = 6 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000.

Структура хранения информации в файле Б аналогична структуре в файле А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, представляющих аномалии, которые возникли в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

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

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

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке – сначала целую часть абсолютной величины произведения Px × 10 000, затем целую часть абсолютной величины произведения Py × 10 000; во второй строке – сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

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

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



Пояснение:
Вначале на основе имеющихся данных построим в Excel для каждого из файлов точечную диаграмму. Для этого необходимо импортировать данные из .txt файла в Excel, выделить столбцы с данными, перейти во вкладку «Вставка» и выбрать пункт «Диаграмма».

Для файла А получим:


Как видно из диаграммы, все точки разбиваются на два кластера, причем для одного кластера все точки находятся выше 10 по оси y, а для второго — ниже.

Для файла В:

Заметим 3 лишние точки, о которых говорится в условии. Их не учитываем при кластеризации. Данные разбиты на 3 кластера. В 1 кластере у всех точек 0 < y < 20, во втором у всех точек y > 20, 10 < x < 18, в третьем 18 ≤ x < 30

Далее в программном коде воспользуемся этой информацией, когда будем группировать точки по кластерам.

На языке программирования Python программа будет выглядеть следующим образом.

import math

def distance(p1, p2):
    return math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)

def sum_distances(point, points):
    return sum(distance(point, p) for p in points)

def find_center(points):
    # Проверяем все возможные комбинации точек как потенциальных центров
    min_sum = float('inf')
    center = None
    for p in points:
        current_sum = sum_distances(p, points)
        if current_sum < min_sum:
            min_sum = current_sum
            center = p
    return center

def process_file_a(filename, cluster_count):
    # Читаем координаты точек
    with open(filename, 'r') as file:
        file = [i.replace(',','.') for i in file.read().splitlines()[1:]]
        points = [tuple(map(float, line.split())) for line in file]
    
    # Разбиваем точки на кластеры
    clusters = [[] for _ in range(cluster_count)]
    for point in points:
        if point[1] > 10:
            clusters[0].append(point)
        else:
            clusters[1].append(point)

    
    # Находим центры кластеров
    centers = [find_center(cluster) for cluster in clusters]
    
    # Вычисляем минимальные координаты центров
    Px = min(c[0] for c in centers)
    Py = min(c[1] for c in centers)
    
    return Px, Py

def process_file_b(filename, cluster_count):
    # Читаем координаты точек
    with open(filename, 'r') as file:
        file = [i.replace(',','.') for i in file.read().splitlines()[1:]]
        points = [tuple(map(float, line.split())) for line in file]
    
    # Разбиваем точки на кластеры
    clusters = [[] for _ in range(cluster_count)]
    for point in points:
        if point[1] > 0 and point[1] < 20:
            clusters[0].append(point)
        elif point[1] > 20 and point[0] > 10 and point[0] < 18:
            clusters[1].append(point)
        elif point[0] >= 18 and point[0] < 30:
            clusters[2].append(point)

    # Находим центры кластеров
    centers = [find_center(cluster) for cluster in clusters]
    
    # Определяем кластер с минимальным и максимальным количеством точек
    cluster_sizes = [len(c) for c in clusters]
    min_size_index = cluster_sizes.index(min(cluster_sizes))
    max_size_index = cluster_sizes.index(max(cluster_sizes))

    # Q1 - расстояние между центрами этих кластеров
    Q1 = distance(centers[min_size_index], centers[max_size_index])

    # Q2 - максимальное расстояние от центра кластера до точки этого кластера
    Q2 = 0
    for i, cluster in enumerate(clusters):
        if cluster: # если кластер не пустой
            center = centers[i]
            max_dist_in_cluster = max(distance(center, p) for p in cluster)
            if max_dist_in_cluster > Q2:
                Q2 = max_dist_in_cluster

    return Q1, Q2

### Обрабатываем файл A
Px_A, Py_A = process_file_a('C:/Users/Александр/Downloads/inf_11_2026/Доп.файлы_ИНФ-11_2026/DEMO_27_A.txt', 2)
print(f"Файл A: Px = {int(abs(Px_A) * 10000)}, Py = {int(abs(Py_A) * 10000)}")

## Обрабатываем файл Б
Q1, Q2 = process_file_b('C:/Users/Александр/Downloads/inf_11_2026/Доп.файлы_ИНФ-11_2026/DEMO_27_B.txt', 3)
print(f"Файл Б: Px = {int(Q1 * 10000)}, Py = {int(Q2 * 10000)}")

Таким образом, дял файла А: 38471 — целая часть абсолютной величины произведения Px × 10 000, 61225 — целая часть абсолютной величины произведения Py × 10 000. Для файла Б: 142058 — целая часть произведения Q1 × 10 000, 25299 — целая часть произведения Q2 × 10 000.

Показать ответ

Источник: Демонстрационный вариант ЕГЭ — 2026
Сообщить об ошибке

Тест с похожими заданиями