670the专题

uva 670The dog task

题意:主人和狗散步,主人走的路都是一段一段的线段,狗想要去有趣的地方,但是要在主人线路上的每个顶点处与主人汇合,而且每次最多只能去一个地方,狗的速度是主人速度的两倍。给定主人的路线(一些坐标点)和狗想去的有趣的地方,求出狗最多能走的路线上的顶点数,并且将这些点打印出来。 分析:对于每一段线段,狗和主人同时出发,然后在另一个端点汇合,其中就看有没有有趣的地方可以去,并且在规定时间里赶回来,也就是狗