📎Задание выполняется с использованием прилагаемых файлов.
Завуч школы установил камеры в столовой и решил проанализировать рассадку учеников. Каждый ученик — точка на плане столовой с координатами (x, y). Завуч заметил, что ученики группируются в компании (кластеры): каждая компания умещается за прямоугольным столом размером H×W. Столы между собой не пересекаются. Стороны столов не обязательно параллельны стенам (столы переставляли на дискотеке и забыли вернуть).
Центром компании называется тот ученик, сумма расстояний от которого до всех остальных в компании минимальна. Гарантируется единственность центра.
Файл А: 2 компании (11А и 11Б), стол 7×6. Не более 1000 учеников. Гарантируется, что в компаниях разное количество учеников (у 11Б всегда больше — они прожорливее).
Файл Б: 3 компании, стол 5×5. Не более 10 000 учеников. Ровно 3 ученика — «перебежчики» (сидят не за своим столом): один ушёл за добавкой, двое — за компотом к другому классу. Их не учитывать.
Для файла А: Px — сумма абсцисс центров, Py — сумма ординат.
Для файла Б: Q1 — мин. расстояние между центрами, Q2 — макс. расстояние.
В ответе: ⌊Px×10000⌋, ⌊Py×10000⌋; ⌊Q1×10000⌋, ⌊Q2×10000⌋.
Завуч подозревает, что 11Б всегда садится максимально далеко от учительского стола. Данные подтверждают.