Условие

Компания «Никола Электроник» проводит полевое испытание новой системы передачи энергии на расстояние – с помощью лазерных энергетических прямопередатчиков (ЛЭП). В отличие от проводов, за счёт сильного лазера энергию можно передавать на большее расстояние. Кроме того, для точек подключения, расположенных на одной прямой, требуется лишь один ЛЭП, что делает технологию менее затратной.

В распоряжении испытательной команды – небольшое рассредоточенное по равнине поселение, которое нужно соединить в единую энергосеть. Вам известны координаты точек подключения (представленные на декартовой плоскости и находящиеся на одной высоте). Соедините их минимальным числом ЛЭП.

Формат входных данных

В первой строке одно целое число N – количество узлов (до 100). Далее N строк, в каждой два вещественных числа – координаты соответствующего узла.

Формат выходных данных

В первой строке одно целое число M – количество проводимых ЛЭП. Далее M строк, в каждой произвольное количество целых номеров узлов в соответствующей ЛЭП.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

 

Разбор

Ключевой особенностью лазеров является то, что если несколько точек лежат на одной прямой, их все можно покрыть одним лучом. Следовательно, задача сводится к минимизации набора прямых, через которые проходят точки на карте.

Первый этап - сбор значимых прямых. Подбираются пары точек, между которыми проводится прямая, проходит анализ, какие ещё точки лежат на этой прямой. В итоге получаем список прямых, каждая из которых описывает группу точек.

Но есть загвоздка - координаты вещественные, следовательно, при работе с ними нельзя делать прямое сравнение, погрешность округления может видоизменять одну и ту же прямую. Поэтому каждую прямую лучше приводить к единому виду.

Второй этап - выбор покрывающего набора. Жадным образом подбираются прямые, покрывающие наибольшее количество точек, они добавляются в ответ, пока не останется ни одной такой прямой. Изолированные точки требуют присоединения к сети отдельными лучами.

Last modified: Wednesday, 13 May 2026, 10:08 AM