P2526 [SHOI2001] Puppy Walk

Grant likes to take his puppy, Pandog, for walks. Grant moves at a constant speed along a fixed route, which may self‑intersect. Pandog enjoys visiting points of interest along the way, but will meet the owner at the given $N$ points. The puppy and the owner start simultaneously from $(X_1, Y_1)$ and finish together at $(X_N, Y_N)$. The puppy’s maximum speed is twice Grant’s speed. While the owner walks in a straight line from one meeting point to the next, Pandog may run to a point of interest. Before each meeting with the owner, Pandog visits at most one point of interest. Your task is to find a route for Pandog (which may partially coincide with the owner’s route) so that it can visit as many points of interest as possible, while still meeting the owner on time at each specified meeting point and at the final rendezvous.

The first line contains two integers $N$ and $M$. The second line contains $N$ 2D integer coordinates, giving Grant’s walking route in order, i.e., the meeting points with Pandog. The third line contains $M$ 2D integer coordinates, giving all points of interest that Pandog is interested in.

Output the puppy’s movement route. The first line contains the number of points visited. The second line contains the 2D coordinates of the visited points in order.

For all testdata, $1 \le N, M \le 100$, all input coordinates are distinct, and their absolute values do not exceed $10^3$. Translated by ChatGPT 5