printЛето 4

printC. Многоугольник

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Представьте себе бесконечную таблицу, строки и столбцы которой пронумерованы, начиная с нуля. Ячейки этой таблицы нумеруются целыми числами как показано на рисунке.
012345678
0025914202735
114812182634
23712182533
3611172432
410162332
5152230
62129
728
8
Такая таблица может быть использована для представления сложных типов данных одним целым числом:
  • Пара целых чисел `(i,\ j)` представляется числом, записанным в ячейке `(i,\ j)`. Например, пара `(3,\ 2)` представляется числом 17. Этот факт записывается как `P_2(3,2)\ =\ 17`.
  • Тройка чисел `(a,\ b,\ c)` представляется как `P_2(a,\ P_2(b,\ c))`. Четвёрка `(a,\ b,\ c,\ d)` представляется как `P_2(a,\ P_2(b,\ P_2(c,\ d)))`. Эту схему можно обобщить для произвольного количества чисел `n`: `P_n(a_1,\ …,\ a_n)\ =\ P_2(a_1,\ P_n-1(a_2,\ …,\ a_n))`, где `P_n` – представление набора из `n` чисел (`n\ ≥\ 2`). Например, `P_3(2,\ 0,\ 1)\ =\ 12`.
  • Список произвольной длины представляется как `L([a_1,\ …,\ a_n])\ =\ P_2(n,\ P_n(a_1,\ …,\ a_n))`. Например, `L([0,\ 1])\ =\ 12`.
Многоугольник, вершины которого имеют неотрицательные целые координаты, есть список `[(x_1,\ y_1),\ …,\ (x_n,\ y_n)]`, который можно представить числом `L([P_2(x_1,\ y_1),\ …,\ P_2(x_n,\ y_n)])`.
Напишите программу, которая по натуральному числу, представляющему простой многоугольник, вычисляет площадь этого многоугольника. Например, треугольник с вершинами `(1,\ 1)`, `(2,\ 0)` и `(0,\ 0)` кодируется числом 2141, его площадь равна 1.
Ввод
Входной файл содержит натуральное число, представляющее многоугольник. Число не превосходит `10^500`. Координаты вершин не превосходят `2^31-1`
Вывод
Запишите в выходной файл площадь многоугольника с одной дробной цифрой.

Пример ввода 1

2141

Пример вывода 1

1.0

Пример ввода 2

206

Пример вывода 2

0.5

Пример ввода 3

157895330

Пример вывода 3

1.0
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading