Входной файл: boundary.in Выходной файл: boundary.out Время на тест: 1 секунда Ограничение на память: 64MB Тесты к задаче:Скачать
Фермер Дон осматривает забор, которым окружено его квадратное плоское поле размером N на N метров (2 £ N £ 500 000). Один угол забора расположен в точке (0, 0), противоположный ему угол находится в точке (N, N). Стороны забора параллельны осям X и Y.
Столбы, к которым крепится забор, стоят не только по углам, но и через метр вдоль каждой стороны поля, всего в заборе 4N столбов. Столбы стоят вертикально и не имеют толщины (радиус равен нулю). Фермер Дон хочет определить, сколько столбов он увидит, если встанет в определенной точке поля.
Проблема заключается в том, что на поле фермера Дона расположено R огромных камней (1 £ R £ 30 000), за которыми не видны некоторые столбы, поскольку Дон недостаточно высок, чтобы смотреть поверх этих камней. Основание каждого камня представляет собой выпуклый многоугольник ненулевой площади, вершины которого имеют целочисленные координаты. Камни стоят на поле вертикально. Камни не имеют общих точек между собой, а также с забором. Точка, где стоит фермер Дон, лежит внутри, но не на границе поля, а также не лежит внутри и на границе камней.
По заданным размеру поля фермера Дона, положению и форме камней на поле, месту, где стоит фермер Дон, вычислите количество столбов, которые может видеть фермер Дон. Если вершина основания камня находится на одной линии с местом расположения Дона и некоторым столбом, то Дон не видит этот столб.
Входные данные: boundary.in
Первая строка входного файла содержит два целых числа N и R, разделенных пробелом.
Вторая строка входного файла содержит два целых числа — координаты X и Y места, где стоит фермер Дон на поле.
Последующие строки входного файла описывают положение R камней:
Описание i-го камня начинается со строки, которая содержит целое число pi (3 £ pi £ 20), определяющее количество вершин в основании камня.
Каждая из последующих pi строк содержит пару разделенных пробелом целых чисел X и Y, которые являются координатами вершины. Вершины основания камня различны между собой и перечислены в направлении против часовой стрелки.
Пример входных данных:
100 1
60 50
5
70 40
75 40
80 40
80 50
70 60
Обратите внимание на то, что
основание камня имеет три
вершины на одной прямой:
(70,40), (75,40) и (80,40).
Выходные данные: boundary.out
Выходной файл должен содержать одну строку с одним целым числом, обозначающим количество столбов, которые будет видеть фермер Дон.
Пример выходных данных:
319
СИСТЕМА ОЦЕНКИ
За каждый тест, на котором ваша программа выведет правильный ответ, вы получите полный балл. Неправильный ответ на тест не оценивается. заборы . мы советуем лучшие камины по выгодным ценам . Лучшие тренажеры. Для вас.