Задание 27. Информатика. ЕГЭ. Шастин. 19.01.2025
- Просмотры: 161
- Изменено: 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
Файл B
