eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ладья

Ладья

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Ладья викингов плывет по бескрайнему океану в поисках Вальгаллы. Руль давно потерян, половина вёсел - и подавно, так что все повороты она может совершить лишь с помощью водоворотов, коих на карте n штук. Но и это не так просто, поэтому и до, и после поворота ладья может направляться только на север, юг, запад либо восток. У первого водоворота начинает она свой путь, и у последнего закончится её путь. Но вот сколько сил останется для последней битвы? Сыграйте против коварного Локи, проложите лучший путь для ладьи. Боги сочтут путь лучшим, если он потребует сил на минимальное количество поворотов, а среди таких ещё и окажется самым коротким. Помните, что в начале пути ладья смотрит на север.

Giriş verilənləri

Первая строка входного файла содержит единственное целое число n. Следующие n строк содержат по два целых числа каждая - координаты соответствующего водоворота. Все водовороты находятся в различных точках. 2n100000, все координаты по модулю не превышают 10^9. Север расположен в направлении увеличения координаты y.

Çıxış verilənləri

Выведите в выходной файл две строки. Первая из них должна содержать два целых числа: искомое минимальное количество поворотов и искомое минимальное расстояние. Вторая же должна содержать описание оптимального пути: номера водоворотов в порядке их прохождения без повторений, начиная с первого и заканчивая последним.

Если ладье суждено блуждать по морю, не находя пути, выведите в единственной строке два числа -1.

Nümunə

Giriş verilənləri #1
3
1 1
1 2
2 2
Çıxış verilənləri #1
1 2
1 2 3
Müəllif Юрий Петров
Mənbə Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B