Задача C. Цветная полоска ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:2 сек
Входной файл:stripe.in   Ограничение памяти:64 Мб
Выходной файл:stripe.out  
Максимальный балл:100  

Условие

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

Более точно: полоска условно делится на квадраты размера 1 × 1 сантиметр. В начале центр первого квадрата фиксируется на столе. На i-м шаге от центра последнего зафиксированного квадрата отступают Ki сантиметров и фиксируют там центр соответствующего квадрата. Затем полоску сгибают в этом месте так, чтобы на месте квадрата, где находится сгиб, образовался прямоугольный треугольник. Полоска сгибается через верх, то есть цвет i-го треугольника не совпадает с цветом i-го отрезка. Затем переходят к следующему шагу.

Сначала полоска выкладывается зеленой стороной вверх.

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

В первой строке входного файла задано число N — количество отрезков, на которых полоску выкладывают прямо. Затем следует N строк, в каждой из которых содержится по два числа Ki и Ti — длина соответствующего отрезка в сантиметрах и сторона, в которую совершается поворот после этого отрезка (1 соответствует повороту вправо, 2 — повороту влево).

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

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

Ограничения

1 ≤ N ≤ 100

Все Ki целые, 1 ≤ Ki ≤ 107.

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

№ Входной файл (stripe.in) Выходной файл (stripe.out)
1 
1
10 1
 
10.00
0.50
2 
2
10 1
20 2
 
10.50
19.50
0.054s 0.009s 13