Задача №111757. The dog task
Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числами (Xi, Yi) декартовыми координатами.
Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке (X1, Y1) и завешает его вместе с хозяином в точке (XN, YN).
Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел (X'j, Y'j). Всего таких мест M. Тем не менее, покидая своего хозяина в точке (Xi, Yi) (где 1 ≤ i ≤ N), Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке (Xi + 1, Yi + 1).
Ваша задача найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки (Xi, Yi) и посещенные интересные места (X'j, Y'j). Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.
Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:
На первой строке через пробел записаны два числа N и M (2 ≤ N ≤ 100, 0 ≤ M ≤ 100). Вторая строка содержит N пар целых чисел X1, Y1, ..., XN, YN, разделенных пробелом, описывающих путь Боба. В третьей строке записано M пар целых чисел, (X'1, Y'1), ... (X'M, Y'M), разделенных пробелом, описывающих интересные места.
Все точки в условии различны и координаты по модулю не превосходят 1000.
В выходном файле должно быть единственное число K количество вершин в оптимальном маршруте Ральфа.
4 5 1 4 5 7 5 2 -2 4 -4 -2 3 9 1 2 -1 3 8 -3
6