Доктор Браун допустил ошибку при выставлении даты на машине времени и Марти МайФлай оказался 2520 году.
Марти, для возвращения назад, должен определить (по карте) столицы двух больших районов Калифорнии.
- Район (кластер) – это группа домов, координаты которых находятся внутри прямоугольника высотой H и шириной W.
Каждый дом обязательно принадлежит только одному району.
- Столица района (или центроид) – это такой дом, сумма манхэттенских расстояний от которого до всех других домов района (кластера) минимальна.
- Манхэттенское расстояние между двумя точками
A(x1,y1) и B(x2,y2) вычисляется по формуле: d(A,B)=∣x2−x1∣+∣y2−y1∣
В файле
27A_... хранятся данные о двух районах Хипл-Вэллии, а в файле
27B_... данные о трех районах Лос-Анджелеса.
Структура файлов с данными одинаковая:
- В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y
(координаты даны в условных единицах; разделителем целой и дробной части может быть запятая)
- Известно, что количество точек не превышает 1000 для файла
27А_... и 10000 для файла 27B_...
- Известно, что высота H и ширина W не более 3
Для каждого файла определите
- координаты столицы (центра) каждого района (кластера),
- затем вычислите два числа:
- Px – среднее арифметическое абсцисс центров кластеров,
- Py – среднее арифметическое ординат центров кластеров.
- В ответе запишите четыре числа:
- в первой строке сначала целую часть произведения Px×10000,
затем целую часть произведения Py×10000 для файла 27A_...,
- во второй строке – аналогичные данные для файла
27B_....