Задание 27. Информатика. ЕГЭ. Поляков-7652
- Просмотры: 116
- Изменено: 24 ноября 2024
(В. Ланская, Р. Ягафаров) Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов 
на картах планет Информатикус и Алгоритмикус. Район (кластер) – это групп населенных пунктов, которые находятся внутри прямоугольника высотой \(H\) и шириной \(W\). Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) – это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле:
$$
d(A, \, B) = | x_2 - x_1| + |y_2 - y_1|
$$
Даны два входных файла (файл A и файл Б). В файле A хранятся данные о точках двух кластеров. В каждой строке записана информация о расположении одной точки: сначала координата \(x\), затем координата \(y\) (в условных единицах). Известно, что количество точек не превышает \(1000\). В файле Б той же структуры хранятся данные о точках трёх кластеров. Известно, что количество точек не превышает \(10~000\). Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) – среднее арифметическое абсцисс центров кластеров, и \(P_y\) – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения \(P_x \times 10~000\), затем целую часть произведения \(P_y \times 10~000\) для файла А, во второй строке – аналогичные данные для файла Б.
Решение:
Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид
Видно, что кластеры можно разделить, прямой \(x = -4\)
Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид
Верхний кластер отделяется от остальных прямой \(y = -4\). Нижние разделяются прямой \(x =-3\).
Python (3.10+)
def which_cluster(point, task):
x, y = point
match task:
case 0:
return int(x > -4)
case 1:
if y > -4:
return 0
elif x < -3:
return 1
else:
return 2
def dist(point1, point2):
x1, y1 = point1
x2, y2 = point2
return abs(x1 - x2) + abs(y1 - y2)
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 = map(float, line.replace(',', '.').split())
data[which_cluster([x, y], t)].append([x, y])
centers = []
for k in range(clusters[t]):
dm = 10**100
c = [0, 0]
for p in data[k]:
d = sum(dist(p, pt) 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] * 10000)
py = int(sum(c[1] for c in centers) / clusters[t] * 10000)
print(px, py)
Ответ:
\(-31374\) \(25065\)
\(-31622\) \(-49268\)