问题3827--小狗散步

3827: 小狗散步

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走,该路线可能自交。Pandog喜欢游览沿途的景点,不过会在给定的N个点和主人相遇。小狗和主人同时从(X1,Y1)点出发,并同时在(Xn,Yn)点汇合。小狗的速度最快是Grant的两倍。当主人从一个点以直线走向另一个点时,Pandog跑向一个它感兴趣的景点。Pandog每次与主人相遇之前最多只去一个景点。 你现在的任务是:为Pandog寻找一条路线(有可能与主人的路线部分相同),使它能够游览最多的景点,并能够准时与主人在给定地点相遇或者汇合。可能有多种方案,但最多景点数量是一样的。

输入

第一行是两个整数N和M( 1≤N,M≤100 ); 第二行的N个坐标给出了Grant的散步路线,即Pandog和主人相遇地点; 第三行的M个坐标给出了所有Pandog感兴趣的景点。   所有输入的坐标均不相同,且绝对值不超过1000。

输出

经过的点数.

样例输入

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

样例输出

6
样例说明:
经过的点数是:
1    4    3    9    5    7    5    2    1    2    -2    4

来源/分类


[提交] [状态]