Задача №112730. The dog task
Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числам ( X i , Y i ) декартовыми координатами.
Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке ( X 1 , Y 1 ) и завешает его вместе с хозяином в точке ( X N , Y N ) .
Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел ( X j ' , Y j ' ) . Всего таких мест M . Тем не менее, покидая своего хозяина в точке ( X i , Y i ) ( где 1 ≤ i ≤ N ) , Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке ( X i + 1, Y i + 1) .
Ваша задача найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки ( X i , Y i ) и посещенные интересные места ( X ' j , Y ' j ) . Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.
Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:
На первой строке через пробел записаны два числа N и M (2 ≤ N ≤ 100, 0 ≤ M ≤ 100) . Вторая строка содержит N пар целых чисел X 1 , Y 1 , ... , X N , Y N , разделенных пробелом, описывающих путь Боба. В третьей строке записано 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