В Битеотианском веревочном парке есть деревья, стоящие друг за другом в длинный ряд за входом. Число дерева 𝑖 растет
𝑥𝑖 метра от входа и на высоте 𝑦𝑖 метра находится станция, которую можно использовать как старт
или конец спуска по веревке. Волею судеб все числа 𝑥𝑖 и 𝑦𝑖 целые.
Руководство парка хотело бы открыть новый выход, который был бы наиболее безопасным, т.е. уклон которого возможен.
наименьший. Как мы знаем из геометрии, угол наклона троса между станцией и станцией 𝑗 будет составлять частное от разницы в высоте.
и разность расстояний между деревьями, т.е. она будет равна | 𝑦𝑖 - 𝑦𝑗
|
| 𝑥𝑖 - 𝑥𝑗
|
(конечно, это не обязательно должно быть целое число).
Поэтому выбирайте такие станции, чтобы минимизировать этот коэффициент - напишите программу, которая читает описание положений возможных станций,
обозначит самый безопасный тросовый спуск и напишет номера станций в стандартный вывод. Однако нас не интересует ситуация.
в котором уклон был бы равен 0, т.е. между равными высотами - после такого спуска двигаться было бы невозможно.
Вход
В первой строке входных данных есть одно натуральное число 𝑁 (1 ≤ 𝑁 ≤ 200 000), которое определяет количество деревьев.
В следующих 𝑁 строках описывается положение следующих деревьев. Описание номера элемента дерева 𝑖 состоит из двух цифр.
неотрицательные целые числа 𝑥𝑖 и 𝑦𝑖 (1 ≤ 𝑥𝑖
, 𝑦𝑖 ≤ 200000), определяя соответственно: расстояние дерева от входа до
метров и высоту в метрах, на которой была обозначена возможная станция выхода. Деревья не нужно указывать в
по возрастанию 𝑥𝑖 - были посажены в разное время, что дало им номера в случайном порядке.
Значения 𝑥𝑖 попарно различны (никакие два дерева не находятся в одном месте). Гарантируется, что существует хотя бы одна пара деревьев разной высоты.
Выход
В первой (единственной) строке вывода должно быть два целых числа 𝑖, 𝑗, (1 ≤ 𝑖, 𝑗 ≤ 𝑁, 𝑖 ≠ 𝑗), обозначающие числа
деревья, между которыми следует протянуть самый безопасный веревочный спуск Если есть много правильных ответов, вы можете
отказаться от подписки на любую из них. Вы также можете распечатать числа 𝑖, 𝑗 в любом порядке.
Оценка
Вы можете решить задачу в нескольких более простых вариантах - некоторые группы тестов имеют дополнительные ограничения.
В таблице ниже показано, сколько баллов получит ваша программа, если она пройдет тесты с этим ограничением.