F. Дракон Лун-Ян
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя и его друг Андрейка только что познакомились с китайской мифологией.
Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов
из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь:
этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную
проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на
Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он
спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной.
Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал
перпендикулярно поверхности. Удержать равновесие дракон может только тогда,
когда существуют две его различные точки, касающиеся стола, такие что
центр масс дракона находится строго между ними.
Вам требуется узнать, сколько было устойчивых положений у дракона,
в которых он мог сохранять равновесие во время сна, если известно,
что форма ломаной в виде которой дракон спит всегда одна и та же.
В первой строке ввода содержится число `n` (`3\ ≤\ n\ ≤\ 1000`) —
количество вершин ломаной и два целых числа `x_c` и `y_c` — координаты
центра масс дракона (`-1000\ ≤\ x_c,\ y_c\ ≤\ 1000`). В следующих
`n` строках содержится по два целых числа `x_i` и `y_i`
(`-1000\ ≤\ x_i,\ y_i\ ≤\ 1000`) — координаты вершин ломаной в порядке обхода против
часовой стрелки (ось `"OX"` направлена вправо, а ось `"OY"` — вверх).
В первой строке выведите число устойчивых
положений дракона.
Пример ввода
9 2 2
1 0
2 1
3 0
4 1
3 3
2 4
1 2
0 3
-1 1
Источник: XI командный чемпионат школьников Санкт-Петербурга по программированию