НачалоПодразделы
Дата и время
22/12/2024 15:14:07
Лето 4
A. Олимпиада B. Оффшорное программирование C. Многоугольник D. Стена E. Сортировка списка F. Разбиение матрицы G. Обобщённые матрёшки H. Узелки I. Цепные дроби J. Унарная система счисления K. Башня
C. Многоугольник
Длинная арифметикаЗадачи на идею
Техника программирования, моделирование
Олимпиадные задачи на русском языке
| 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
