Задача G. Кусочно-линейная функция

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k1|x + b1| + k2|x + b2| + ...  + kn|x + bn|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

Входной файл содержит целое число n, за которым следуют n пар целых чисел ki bi.

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

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

Линейные функции должны быть перечислены в порядке возрастания соответствующих им интервалов оси x.

Ограничения

1 ≤ n ≤ 1000.

|ki|, |bi| ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1 1
2
-1 -1
1 1
2
2
1 2 3 2
2
-4 -8
4 8
3
2
2 2 -2 2
1
0 0

0.104s 0.015s 13