Олимпиадный тренинг

Задача . ЕГЭ СТ-Хард. Задание 27. Кластеризация


Задача

Темы:

На плоскости задано множество точек. Известно, что точки образуют несколько кластеров. Точки одного кластера расположены внутри прямоугольника размером не более H×W (стороны не обязательно параллельны осям координат). Кластеры не пересекаются.

Файл А

Файл points_a.csv (≤ 1000 точек, 2 кластера, H=10, W=6). Определите:

  1. Количество точек в большем кластере.
  2. Сумму координат x всех точек меньшего кластера, округлённую до целого.

Файл Б

Файл points_b.csv (≤ 10 000 точек, 3 кластера, H=6.5, W=5; 6 точек-выбросов не принадлежат ни одному кластеру). Определите:

  1. Количество точек, не принадлежащих ни одному кластеру (выбросов).
  2. Координату x медоида наибольшего кластера (точки с минимальной суммой расстояний до остальных точек этого кластера), округлённую до целого.

В ответе для каждого файла запишите два числа через пробел.


time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя