Задача №2908. Гаджеты
Товарищ Иванов — очень богатый любитель гаджетов. Недавно он понял, что не может купить всех гаджетов, которые он хочет потому что их никто не производит. Поэтому он решил построить свою собственную Фабрику Гаджетов.
Фабрика Гаджетов будет построена на Сколковском шоссе. На этом шоссе сконцентрировано производство нанотехнологичной продукции, необходимой для производства гаджетов. Сколковское шоссе представляет собой прямую, а фабрики — точки на этой прямой (фабрики расположены вдоль дороги).
Для производства гаджета необходимо N нанотехнологичных деталей, M фабрик производит эти детали. Товарищ Иванов хочет минимизировать сумму квадратов расстояний до ближайших фабрик, производящих необходимые детали. Помогите ему и найдите все точки для которых эта сумма минимальна.
Первая строка входного файла содержит два натуральных числа N и M (1 ≤ n ≤ 10000; N≤ M ≤ 100000)
Следующие M строк содержат пары чисел xi и pi, xi – координата i-ой фабрики, а pi – идентификатор детали, которую производит данная фабрика (xi ≤ 100000; xi ≤ xi +1; 1 ≤ pi ≤ N).
Для каждой детали существует хотя бы одна фабрика, которая производит эту деталь.
Первая строка выходного файла должна содержать целое число K — количество точек, где может быть расположена Фабрика Гаджетов.
Следующие K строк должны содержать координаты этих точек в возрастающем порядке. Значения должны выводится с точность 10-6.
3 5 -1 3 0 1 2 3 4 2 5 2
1 2.0
2 5 1 1 2 2 3 1 4 2 5 1
4 1.5 2.5 3.5 4.5