Codeforces Round 328 (Div. 2) |
---|
Закончено |
Чудовище Ари всегда просыпается очень рано, с первыми лучами солнца, и первым делом идёт кормить свою белочку.
Ари рисует правильный выпуклый многоугольник на полу и пронумеровывает его вершины числами 1, 2, ..., n в порядке обхода по часовой стрелке. Затем, начиная с вершины 1, она рисует лучи в направлении всех остальных вершин. Каждый луч останавливается, когда достигает вершины, в которую направлен, или когда он пересекается с другим лучом, нарисованным ранее. Ари повторяет этот процесс для вершин 2, 3, ..., n (в таком порядке), а затем кладёт грецкий орех в каждую область, образовавшуюся внутри многоугольника.
Белочка Ада хочет собрать все грецкие орехи, но ей не разрешается наступать на линии, нарисованные Ари. Это значит, что Аде надо сделать маленький прыжок, если ей нужно попасть из одной области в другую. Прыжки у Ады очень короткие, поэтому она может прыгнуть из одной области P в другую область Q тогда и только тогда, когда P и Q имеют общую сторону или угол.
Ада начинает за границами исходного многоугольника. Какое минимальное количество прыжков ей надо сделать, чтобы собрать все орехи?
В первой и единственной строке ввода записано единственное целое число n (3 ≤ n ≤ 54321) — количество вершин в правильном многоугольнике, нарисованном Ари.
Выведите минимальное количество прыжков, необходимых Аде для того, чтобы собрать все грецкие орехи. Обратите внимание, что ей нет необходимости покидать многоугольник после этого.
5
9
3
1
Одно из возможных решений для первого примера показано на рисунке выше.
Название |
---|