M. Обход бункеров
2000 мс · 256 МБ · всё или ничего
Во дворе бункеров, заданных точками. Нужно обойти все бункеры по одному разу и вернуться в начальный, двигаясь между ними по прямым. Маршрут не должен дважды проходить через одну точку: звенья не пересекаются и не касаются друг друга — кроме общих концов у соседних звеньев.
Начинать можно с любого бункера. Если маршрута не существует, так и сообщите.
Формат ввода
В первой строке — число (). В следующих строках — целые координаты бункеров (). Никакие два бункера не совпадают.
Формат вывода
Выведите номеров бункеров в порядке обхода или строку No solution, если маршрута нет.
Примеры
ввод
4 0 0 0 1 1 0 1 1
вывод
1 3 4 2
ввод
3 0 0 0 1 0 2
вывод
No solution
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.