Dog Days

Time limit1sMemory limit128 MB

Summary
Given bunkers on a plane and a speed and survival-time limit, find the minimum number of intermediate bunkers a chicken must visit to reach a target bunker, or report it cannot escape.
Level

Medium5 of 10

Topics
Graph, BFS, Shortest path
Solved
No attempts yet

Problem

It is the dog days of summer.

Haebin is trying to catch a chicken for a boneless-chicken party, but one brave chicken is running away.

The chicken can move at v meters per second. It escapes safely if it reaches the destination bunker at (xt, yt) from its current position (xs, ys). On the way, the chicken may hide in other bunkers, but after leaving a bunker it is caught if it stays outside for m minutes or longer.

Determine whether the chicken can reach the destination bunker.

Input

The first line contains the chicken's speed v and survival time m.

The second line contains the starting position xs ys, and the third line contains the destination bunker position xt yt.

Each remaining line until end of file contains the coordinates x y of one intermediate bunker.

All distances are measured in meters. There are at most 1,000 intermediate bunkers, and every coordinate is between -10,000 and 10,000, inclusive.

Output

If the chicken can reach the destination bunker, print Yes, visiting n other holes.. Here, n is the minimum number of intermediate bunkers that must be visited.

If escape is impossible, print No..

Examples1

  1. Example 1

    Input
    3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000
    Expected output
    Yes, visiting 2 other holes.