小狗散步
成绩 | 100 | 开启时间 | 2020年06月18日 星期四 17:55 |
折扣 | 0.8 | 折扣时间 | 2020年06月18日 星期四 17:55 |
允许迟交 | 是 | 关闭时间 | 2020年06月18日 星期四 17:55 |
输入文件 | dog.in | 输出文件 | dog.out |
【题目描述】小狗散步(dog)SHOI2001上海市选拔赛
琳琳养了一条宠物小狗Candy,琳琳喜欢带着她的小狗Candy散步。琳琳以一定的速度沿着固定路线走,该路线可能自交。Candy喜欢游览沿途的景点,不过会在给定的N个点和主人相遇。小狗和琳琳同时从(X1,Y1)点出发,并同时在(Xn,Yn)点汇合。小狗的速度最快是琳琳的两倍。当主人从一个点以直线走向另一个点时,Candy跑向一个它感兴趣的景点。Candy每次与琳琳相遇之前最多只去一个景点。
你现在的任务是:为Candy寻找一条路线(有可能与主人的路线部分相同),使它能够游览最多的景点,并能够准时与主人在给定地点相遇或者汇合。
【输入格式】
输入第一行是两个整数N和M(1≤N,M≤100);
输入第二行的N个坐标给出了琳琳的散步路线,即Candy和主人相遇地点;
输入第三行的M个坐标给出了所有Candy感兴趣的景点。
所有输入的坐标均不相同,且绝对值不超过1 000。
【输出格式】
输出小狗的移动路线。
第一行是经过的点数,第二行依次为经过的点的坐标(直角坐标系)。
【输入样例】
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
【注意事项】
答案不一定唯一。