TopCoder problem "HexagonIntersections" used in SRM 206 (Division I Level Three)



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.

 

Definition

    
Class:HexagonIntersections
Method:count
Parameters:int, int, int, int
Returns:int
Method signature:int count(int x0, int y0, int x1, int y1)
(be sure your method is public)
    
 

Constraints

-x0, y0, x1, and y1 will be between -10000 and 10000, inclusive.
-(x0,y0) and (x1,y1) will not be the same point.
 

Examples

0)
    
1
-2
3
1
Returns: 4
A line between the centers of hexagons (1,-2) and (3,1) intersects 4 hexagons:
1)
    
-2004
-1002
-2000
-1000
Returns: 3
This line is coincident with the edges of several hexagons, but it only intersects the interior of three:
2)
    
54
93
64
95
Returns: 11
3)
    
0
0
19
20
Returns: 26
4)
    
0
0
19
-20
Returns: 40

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2920

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5852&pm=2920

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Geometry