Информатика. ЕГЭ

Задания для подготовки

Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников

Перейти к заданиям

Задание 27. Информатика. ЕГЭ. Шастин. 19.01.2025

Просмотры: 678

Изменено: 1 февраля 2025

(Д. Бахтиев) Компания «Энергосеть» занимается оптимизацией энергоснабжения в нескольких регионах. Для этого нужно определить местоположение главных трансформаторных узлов, которые обеспечат минимальные потери при распределении энергии. В каждом регионе имеются несколько подрегионов, каждый из которых характеризуется тем, что расстояние от любой точки в подрегионе до точки из другого подрегиона не менее $R$ условных единиц. Необходимо определить место для трансформаторного узла, которое находится за два шага: сначала для каждого подрегиона нужно найти его центр нагрузки — такую точку в регионе, от которой суммарное расстояние до всех остальных точек подрегиона минимально. Затем, учитывая данные о центрах нагрузки всех подрегионов, найти центральный трансформаторный узел — такая точка в одном из регионов, от которой суммарное расстояние до всех центров нагрузки минимально. Расстояние между двумя точками $(x_1, \, y_1)$ и $(x_2, \, y_2)$ на плоскости вычисляется по формуле Евклида: $$ d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$ Файл 27_A.txt содержит данные о точках двух регионов. Файл 27_B.txt содержат данные о точках трёх регионов. В первой строке каждого файла записано значения $R.$ В каждой из следующих строк записаны координаты $x$ и $y$ очередной точки. Количество точек в файле 27_A.txt не превышает $1000,$ в 27_B.txtне превышает $10000.$

Для каждого региона определить координаты центрального трансформаторного узла. В ответе укажите четыре целых числа. В первой строке: ближайшие целые числа значений произведения $x$-координаты узла на $10000$ и $y$-координаты узла на $10000$ для региона А. Во второй строке: аналогичные данные для региона В.

Файл с данными

Решение:

Python


from math import dist
from turtle import *

def visualize(clusters):
    tracer(0)
    up()
    ht()
    screensize(2500, 2500)
    k = 40
    colors = ('red', 'green', 'blue', 'orange')
    for col, cl in zip(colors, clusters):
        for p in cl:
            x, y = p
            goto(x * k, y * k)
            dot(3, col)
    update()

base = ''
files = ['27_A.txt', '27_B.txt']

for task in (0, 1):
    fd = open(base + files[task])
    eps = float(fd.readline().replace(',', '.'))
    data = [tuple(map(float, line.replace(',', '.').split())) for line in fd]
    clusters = []
    while data:
        clusters.append([data.pop()])
        for p in clusters[-1]:
            neigh = [pt for pt in data if dist(p, pt) < eps]
            clusters[-1] += neigh
            for pt in neigh:
                data.remove(pt)
    #print(len(clusters), [len(c) for c in clusters])
    #if task == 1: visualize(clusters)
    centers = []
    for cl in clusters:
        dmin = float('inf')
        for p in cl:
            d = sum(dist(p, pt) for pt in cl)
            if d < dmin:
                dmin = d
                c = p
        centers += [c]
    dmin = float('inf')
    cl = []
    for x in clusters:
        cl += x
    for p in cl:
        d = sum(dist(p, pt) for pt in centers)
        if d < dmin:
            dmin = d
            central_trans = p
    x = round(10_000 * central_trans[0])
    y = round(10_000 * central_trans[1])
    print(x, y)

Ответ:
$58917$ $-602$
$101947$ $210484$

Визуализация кластеров с помощью графики модуля Turtle

Файл A