AIOC Banner

Problem: Rock Climbing

Want to try solving this problem? You can submit your code online if you log in or register.

Rock Climbing

Time Limit: 1 second
Memory Limit: 64 Mb

For reasons not yet understood, indoor rock climbing is becoming a popular pastime amongst many ex-philatelists, philanthropists and philosphers. You too have decided to follow suit and begin your career aspirations as the world's best rock climber. Indoor rock climbing involves getting from the bottom of a wall to the top using only your strength to pull yourself up, and trying your utmost not to fall off. Near the top of the wall is a bell that you ring to boast your feat to the world.

The wall is a flat two-dimensional surface with handles at various points. To hang onto the wall, you must have a hold on three distinct handles when you are stationary, or two distinct handles when you are moving--any fewer and you will fall off and embarass yourself!

To move yourself around and up the wall, you can let go of one of these three handles and then take hold of a different handle. The time required to perform the move is equal to the sum of the horizontal and vertical distance moved between the handle you let go of and the handle you take hold of.

As you can only reach so far, each of the three handles you are attached to must be at most R metres from some other handle you are attached to, as measured by the sum of the horizontal and vertical distances between two points. Note that they do not all have to be within R metres of each other. For example, the starting configuration in the diagram below (shown by the dotted line) has distance 2 between points 1 and 2, and distance 2 between points 2 and 4, but distance 4 between points 1 and 4. This is a valid configuration even if R = 2.

In order to be the world's fastest rock climber, you need to determine a set of moves that will get you to the bell as fast as possible. The bell is located on one of the handles (but is not necessarily the highest handle). You are told which handles to begin your climb from and you are guaranteed that these will all be within reach of each other.

Given (i) the set of handles on a wall described as (x,y) co-ordinates on a plane and (ii) your starting handles, your task is to find the smallest time in which you can get from the starting position to the bell on the wall.

For example, consider the diagram above with R = 2. Each circle represents a handle. There are 16 handles (including the one with the bell). Suppose we were required to start by having a hold on handles 1, 2 and 4 as shown. Then one possible way to reach the bell would be to:

This takes a total of 1+3+3+4+6+6 = 23 seconds, and is in fact the fastest way to reach the bell.


For 50% of the marks, N <= 20.


Your program must read from standard input. The first line of input will contain the integers N R, separated by a space. The N handles will be numbered 1 ...N. The second line will contain the three distinct integers A B C that denote the three handles you begin from (1 <= A,B,C, <= N).

Following this will be N lines in the form x_i y_i, where the ith of these lines describes the location of the ith handle. No two handles will have the same location. The bell is always attached to the Nth handle.


Your program must write a single line to standard output. This line must contain a single integer, giving the smallest possible time to get from the starting position to the bell. You are guaranteed that it will always be possible to reach the bell.

Sample Input

16 2
1 2 4
4 1
5 2
6 2
7 2
5 3
8 3
3 4
5 5
8 4
9 5
6 6
4 6
9 7
6 7
6 8
8 8

Sample Output



The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2024

Page generated: 27 February 2024,  1:25am AEDT