Задача C. Крайние проекции ≡

Условие

Глеб нарисовал на координатной плоскости N точек и стал проецировать их в разных направлениях на ось ординат.

Сначала Глеб выбирает направление проецирования — наклоняет линейку под определённым углом. Затем, параллельно перемещая линейку, Глеб прикладывает её по очереди ко всем точкам и для каждой точки находит точку пересечения линейки с осью ординат. Эта точка пересечения и есть проекция точки на ось ординат.

Глеб проецирует точки на ось ординат во всех возможных направлениях. Сначала он располагает линейку вертикально, а затем начинает разворачивать её против часовой стрелки. При этом угловой коэффициент наклона линейки возрастает от −∞ до +∞.

При каждом направлении проектирования найдётся точка, которая спроецируется "выше всех" (будет иметь наибольшую ординату проекции). Назовём такую точку крайней точкой.

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество точек.

Далее следуют N строк, каждая из которых содержит пару вещественных чисел x_i y_i — координаты точки.

Формат выходного файла

Выходной файл должен содержать (2 M+1) чисел, где M — количество изменений крайней точки.

Первое число — это номер точки, которая будет крайней при угловом коэффициенте наклона линейки, стремящемся к −∞. Далее идут M пар чисел k_i j_i — угловой коэффициент наклона линейки, при котором происходит изменение крайней точки, и номер точки, которая станет крайней после изменения. Пары чисел должны быть выведены в порядке возрастания углового коэффициента.

Угловой коэффициент должен быть выведен с точностью не менее 3-х знаков после запятой.

Ограничения

1 ≤ N ≤ 1000

1 ≤ x_i, y_i ≤ 100

Гарантируется, что при любом угловом коэффициенте выше всех не могут проецироваться более двух точек.

Примеры тестов

10
5.0 3.0
6.5 2.5
9.0 2.0
3.5 4.0
1.0 3.1
7.5 1.75
2.0 2.6
6.0 3.5
10.0 1.0
9.0 1.2

9
-1.000 3
-0.500 8
-0.200 4
0.360 5