Сколько вершин видно
1000 мс · 256 МБ · всё или ничего
Дан выпуклый многоугольник (вершины против часовой стрелки) и точка строго снаружи. Посчитайте, сколько вершин многоугольника видно из этой точки: вершина видна, если отрезок до неё не проходит через внутренность многоугольника.
Формат ввода
В первой строке — число (). В следующих строках — вершины против часовой стрелки. В последней строке — координаты точки, лежащей строго снаружи. Координаты целые, по модулю не больше .
Формат вывода
Выведите количество видимых вершин.
Примеры
ввод
4 -1 -1 1 -1 1 1 -1 1 5 0
вывод
2
ввод
4 -1 -1 1 -1 1 1 -1 1 5 5
вывод
3
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.