Задание 27. Информатика. ЕГЭ. Поляков-7654
- Просмотры: 149
- Изменено: 25 ноября 2024
(М. Крючков) В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки. 
После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера. Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева. Расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле:
$$
d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
$$
В каждом кластере нужно найти оптимальную точку сбора (центр), такую что суммарная стоимость доставки в это место всех спиленных деревьев данного кластера минимальна. Аномалиями назовём совокупности из не более чем \(10\) точек, каждая из которых находится на расстоянии более \(30\) м от точек кластеров. Аномалии в расчётах не учитываются. Даны два входных файла (файл A и файл Б). В файле A хранятся данные о двух кластерах. Каждый кластер имеет форму прямоугольника размером \(100 \times 100\) м. Каждая строка файла содержит три характеристики одного дерева: координату \(x\), затем координату \(y\) и затем высоту дерева. Количество деревьев в каждом кластере не превышает \(1000\). В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером не более \(100 \times 200\) м. Количество точек в каждом кластере не превышает \(10~000\).
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 100~000\), затем целую часть произведения \(P_y \times 100~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что левый кластер можно отделить прямой \(x = 160\), а правый — прямой \(x = 340\).
Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид
Кластер \(0\) находится в прямоугольнике \(75 < x < 225\), \(-125 < y < 125\). Кластер \(1\) находится в прямоугольнике \(-125 < x < 25\), \(-25 < y < 125\). Кластер \(2\) находится в прямоугольнике \(-275 < x < -25\), \(-175 < y < -25\).
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
if x < 160:
return 0
elif x > 340:
return 1
return -1
case 1:
if 75 < x < 225 and -125 < y < 125:
return 0
elif -125 < x < 25 and -25 < y < 125:
return 1
elif -275 < x < -25 and -175 < y < -25:
return 2
return -1
def dist(point1, point2):
x1, y1 = point1
x2, y2 = point2
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
base = ''
files = ['27A.txt', '27B.txt']
clusters = [2, 3]
for t in [0, 1]:
fd = open(base + files[t])
fd.readline()
data = [[], [], []]
for line in fd:
x, y, h = map(float, line.replace(',', '.').split())
cl = which_cluster([x, y], t)
if cl > -1:
data[cl].append([x, y, h])
centers = []
for k in range(clusters[t]):
dm = 10**100
c = [0, 0]
for p in data[k]:
d = sum(dist(p[:2], pt[:2]) * pt[2] for pt in data[k])
if d < dm:
dm = d
c = p
centers.append(c)
px = int(sum(c[0] for c in centers) / clusters[t] * 100000)
py = int(sum(c[1] for c in centers) / clusters[t] * 100000)
print(px, py)
Ответ:
\(25667971\) \(24175730\)
\(-1659383\) \(-1838931\)