НачалоПодразделы
Другие разделы
Дата и время
21/11/2024 23:34:55
956. Многоугольник
Многоугольник
Длинная арифметикаЗадачи на идею
Техника программирования, моделирование
Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 4C) |
| 09/07/2008 | Лето 2008 - 4 (C) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Представьте себе бесконечную таблицу, строки и столбцы которой пронумерованы, начиная с нуля. Ячейки этой таблицы нумеруются целыми числами как показано на рисунке.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 2 | 5 | 9 | 14 | 20 | 27 | 35 | … |
| 1 | 1 | 4 | 8 | 12 | 18 | 26 | 34 | … | |
| 2 | 3 | 7 | 12 | 18 | 25 | 33 | … | ||
| 3 | 6 | 11 | 17 | 24 | 32 | … | |||
| 4 | 10 | 16 | 23 | 32 | … | ||||
| 5 | 15 | 22 | 30 | … | |||||
| 6 | 21 | 29 | … | ||||||
| 7 | 28 | … | |||||||
| 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
