НачалоПодразделы
Другие разделы
Дата и время
09/04/2025 15:32:46
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. Этот факт записывается как P2(3,2) = 17.
- Тройка чисел (a, b, c) представляется как P2(a, P2(b, c)). Четвёрка (a, b, c, d) представляется как P2(a, P2(b, P2(c, d))). Эту схему можно обобщить для произвольного количества чисел n: Pn(a1, …, an) = P2(a1, Pn-1(a2, …, an)), где Pn – представление набора из n чисел (n ≥ 2). Например, P3(2, 0, 1) = 12.
- Список произвольной длины представляется как L(a1 … an) = P2(n, Pn(a1, …, an)). Например, L(0 1) = 12.
Многоугольник, вершины которого имеют неотрицательные целые координаты, есть список
[(x1, y1), …, (xn, yn)], который можно представить числом L(P2(x1, y1) … P2(xn, yn)).
Напишите программу, которая по натуральному числу, представляющему простой многоугольник, вычисляет площадь этого многоугольника. Например, треугольник с вершинами (1, 1), (2, 0) и (0, 0) кодируется числом 2141, его площадь равна 1.
Ввод
Входной файл содержит натуральное число, представляющее многоугольник. Число не превосходит 10500. Координаты вершин не превосходят 231-1
Вывод
Запишите в выходной файл площадь многоугольника с одной дробной цифрой.
Пример ввода 1
2141
Пример вывода 1
1.0
Пример ввода 2
206
Пример вывода 2
0.5
Пример ввода 3
157895330
Пример вывода 3
1.0
