Двойственная ломаная
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
Пусть задана некоторая замкнутая ломаная P. Двойственной для P ломаной называется ломаная, вершины которой находятся в серединах звеньев P.
Определим понятие двойственной для P ломаной k-ого порядка dual(P, K) следующим образом:
- двойственной ломаной нулевого порядка является сама ломаная P (dual(P, 0) = P);
- если K > 0, то двойственной ломаной K-ого порядка является ломаная, двойственная для dual(P, K - 1).
Задана замкнутая ломаная P и число K. Найдите длину двойственной для P ломаной k-ого порядка dual(P, K).
Входные данные
Входной файл INPUT.TXT содержит число звеньев исходной ломаной N (3 ≤ N ≤ 100). Каждая из последующих N строк содержит по два целых числа xi и yi - координаты i-ой вершины ломаной. Все xi и yi не превосходят 105 по абсолютной величине. Последняя строка входного файла содержит целое число K (0 ≤ K ≤ 10).
Выходные данные
В выходной файл OUTPUT.TXT выведите искомую длину с точностью не хуже, чем 10-4.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
0 0
1 0
1 1
0 1
0
| 4 |
| 2 | 4
0 0
1 0
1 1
0 1
1
| 2.8284271247 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
