Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
CF0003 - БЕЛОЧКА И ЧУДОВИЩЕ |
Чудовище Ари всегда просыпается очень рано, с первыми лучами солнца, и первым делом идёт кормить свою белочку.
Ари рисует правильный выпуклый многоугольник на полу и пронумеровывает его вершины числами 1, 2, ..., n в порядке обхода по часовой стрелке. Затем, начиная с вершины 1, она рисует лучи в направлении всех остальных вершин. Каждый луч останавливается, когда достигает вершины, в которую направлен, или когда он пересекается с другим лучом, нарисованным ранее. Ари повторяет этот процесс для вершин 2, 3, ..., n (в таком порядке), а затем кладёт грецкий орех в каждую область, образовавшуюся внутри многоугольника.
Белочка Ада хочет собрать все грецкие орехи, но ей не разрешается наступать на линии, нарисованные Ари. Это значит, что Аде надо сделать маленький прыжок, если ей нужно попасть из одной области в другую. Прыжки у Ады очень короткие, поэтому она может прыгнуть из одной области P в другую область Q тогда и только тогда, когда P и Q имеют общую сторону или угол.
Ада начинает за границами исходного многоугольника. Какое минимальное количество прыжков ей надо сделать, чтобы собрать все орехи?
Входные данные.
В первой и единственной строке ввода записано единственное целое число n (3 ≤ n ≤ 54321) — количество вершин в правильном многоугольнике, нарисованном Ари.
Выходные данные.
Выведите минимальное количество прыжков, необходимых Аде для того, чтобы собрать все грецкие орехи. Обратите внимание, что ей нет необходимости покидать многоугольник после этого.
Примеры.
N |
stdin |
stdout |
1 |
5 |
9 |
2 |
3 |
1 |
Ավելացրեց. | Հրանտ Հովհաննիսյան |
Ամսաթիվ. | 2016-05-20 |
Ժամանակի սահմանափակումը. | 1s |
Ծրագրի տեքստի սահմանափակումը. | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK JS-MONKEY NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
Աղբյուրը. | CODEFORCES |