НачалоПодразделы
Другие разделы
Дата и время
05/04/2025 16:51:52
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, представляется числом, записанным в ячейке (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
