«Прогулка»
Условие
Хозяин вышел на прогулку с собакой. Известно, что путь хозяина представляет собой ломаную линию, координаты отрезков ломаной заданы:
(Xi,Yi), i=1,…,N.
Точка (X1,Y1) – начальная точка ломаной линии, а точка (XN,YN) – конечная точка ломаной. Хозяин двигается во время прогулки от стартовой точки, далее по отрезкам ломаной линии и заканчивает путь в конечной точке ломаной. У собаки есть свои любимые места (координаты любимых мест заданы: (Xdogj,Ydogj), j=1,…,M), которые собака хотела бы посетить. В то время, пока хозяин проходит один отрезок ломаной, собака может посетить только одно из своих любимых мест. В начальной и конечной точке ломаной, а также когда хозяин проходит каждую точку изгиба ломаной, собака обязана подбежать к хозяину. Известно, что скорость собаки в два раза выше скорости хозяина. Необходимо определить, какое наибольшее количество своих любимых мест сможет посетить собака за время прогулки.
Входные данные
Входные данные находятся в файле input.txt.
· Первая строка содержит два числа: N - количество точек ломаной (включая начальную и конечную точки пути) и M – количество любимых мест собаки.
· Начиная со второй строки идут координаты точек ломаной: сначала координата x, а затем координата y и т. д. (координаты точек ломаной следуют в строке в той последовательности, в которой они соединяются отрезками, начиная от начальной точки и заканчивая конечной; все числа разделяются пробелами). Информация о точках ломаной может занимать несколько строк.
· Начиная с новой строки, следуют координаты любимых мест собаки: сначала координата x, а затем координата y и т. д. (все числа идут через пробел). Информация о координатах любимых мест может занимать несколько строк.
Выходные данные
Выходные данные должны быть подготовлены в файле output.txt.
· Первая строка содержит два числа (через пробел). Первое число l – максимальное количество мест, которые сможет посетить собака за время прогулки (это и все точки ломаной и некоторые любимые места собаки). Второе число dog – максимальное количество любимых мест собаки, которые она смогла посетить.
Пример входных данных
2 1
0 0 2 2
3 3
Пример выходных данных
3 1