Triangular Grid |
A single triangle in this grid is a triangle with vertices on intersections of grid lines that has not other triangles inside it.
Given two points P and Q in the Cartesian plane you must determine how many single triangles are intersected by the segment . A segment intersects a polygon if and only if there exists one point of the segment that lies inside the polygon (excluding its boundary).
Note that the segment in the example intersects exactly six single triangles.
The problem input consists of several cases, each one defined in a line that contains six integer values B, H, x1, y1, x2 and y2 ( 1 B 200, 2 H 200, -1000 x1, y1, x2, y2 1000), where:
You can suppose that neither P nor Q lie in the boundary of any single triangle, and that P Q.
The end of the input is specified by a line with the string ``0 0 0 0 0 0''.
For each case in the input, print one line with the number of single triangles on the grid that are intersected by the segment .
100 120 -20 -100 160 160 10 8 5 5 5 4 10 8 5 5 10 5 10 8 5 5 10 10 0 0 0 0 0 0
6 1 2 3