ACM Problem B

ACM 2000, Greater New York, Problem B

This page explains how to solve Problem B of the ACM Programming Contest 2000, Greater New York region. For reference, here's the PDF statement of the problem.

First of all, we have to find the coordinates of the centers of the hexagons. The following figure shows a grid of points superimposed on the hexagonal grid. We denote the coordinates of the points as (K, L), where K and L are integers.

As we can see, the points are the centers of the hexagons only when K and L have the same parity.

The coordinates (x, y) of the point (K, L) are given by the formulas:
x = 3 K n/2
y = sqrt(3) L n/2
where n is the side of the hexagons.

Our first task is, given a point (x, y), to find the coordinates (K, L) of the hexagon it belongs to. We can use the function floor() (from math.h) to find the point (K, L) immediately to the bottom left of (x, y). Now, two things could happen: either (K, L) is the center of an hexagon, or it isn't, depending on its parity. In each case, we have to compare the distance from (x, y) to two different points (using the Pythagorean Theorem). The shortest distance will indicate the hexagon to which the point belongs.

Once we have the (K, L) coordinates of the starting and ending hexagons, we have to find the number of hexagons the bee has to jump to get from one to the other. Each step has length sqrt(3)*n. The path always has an L shape (unless the hexagons are aligned in a straight line, in which case the path is just a straight line). There are two possibilities: either the path goes first diagonally down and then diagonally up, or first diagonally and then vertically:

The first case can be identified by the condition:
abs(L2-L1) < abs(K2-K1)
and the second case, by the condition:
abs(L2-L1) > abs(K2-K1)

In the first case, the number of steps is:
abs(K2-K1)
In the second, it is:
abs(K2-K1) + (abs(L2-L1) - abs(K2-K1))/2

Finally, we note there is a special case: If both points fall on the same hexagon, then, instead of travelling from the first point to the hexagon's center and then to the second point, we must travel directly from one point to the other. This is indicated by one of the examples given:
9 1 4 5 1
where the answer given is 5.000.

The complete solution code? You can write it yourself!

The above graphics were created with MiniCad 6.

Home page