HexagonIntersections
SRM 206 · 2004-08-04 · by legakis
Problem Statement
A hexagonal grid is a tiling of the plane consisting solely of regular hexagons. You will be given two pairs of coordinates, identifying two hexagons in the grid. Consider a line segment connecting the centers of these two hexagons, and return the number of hexagons that this line segment intersects.
Only count hexagons if the line passes through their interior. Do not count a hexagon if the line only intersects one of its corners or is coincident with one of its edges.
Hexagons will be identified by a pair of coordinates, as shown in the following diagram. The first coordinate is proportional to the horizontal distance from the vertical axis. The second coordinate is proportional to the vertical distance from the diagonal axis.
Constraints
- x0, y0, x1, and y1 will be between -10000 and 10000, inclusive.
- (x0,y0) and (x1,y1) will not be the same point.
1 -2 3 1 Returns: 4
A line between the centers of hexagons (1,-2) and (3,1) intersects 4 hexagons:
0 0 1 0 Returns: 2
0 0 1 1 Returns: 2
0 0 0 1 Returns: 2
0 0 -1 0 Returns: 2
-2004 -1002 -2000 -1000 Returns: 3
This line is coincident with the edges of several hexagons, but it only intersects the interior of three:
Submissions are judged against all 43 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HexagonIntersections with a public method int count(int x0, int y0, int x1, int y1) · 43 test cases · 2 s / 256 MB per case