eolymp
bolt
Try our new interface for solving problems
Problems

Triangular Grid

Triangular Grid

There is an infinite grid in the Cartesian plane composed of isosceles triangles, with the following design: \includegraphics{https://static.e-olymp.com/content/ec/ecc7cfe11eac8975f5c185511ecb69e541ed3957.jpg} A single triangle in this grid is a triangle with vertices on intersections of grid lines that has not other triangles inside it. \includegraphics{http://uva.onlinejudge.org/external/116/11662img2.png} Given two points \textbf{P} and \textbf{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). \includegraphics{http://uva.onlinejudge.org/external/116/11662img2.png} Note that the segment in the example intersects exactly six single triangles. \InputFile The problem input consists of several cases, each one defined in a line that contains six integer values \textbf{B}, \textbf{H}, \textbf{x_1}, \textbf{y_1}, \textbf{x_2} and \textbf{y_2} (\textbf{1} ≤ \textbf{B} ≤ \textbf{200}, \textbf{2} ≤ \textbf{H} ≤ \textbf{200}, \textbf{-1000} ≤ \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} ≤ \textbf{1000}), where: \begin{itemize} \item \textbf{B} is the length of the base of all isosceles single triangles of the grid. \item \textbf{H} is the height of all isosceles single triangles of the grid. \item (\textbf{x_1}, \textbf{y_1}) is the point \textbf{P}, that defines the first extreme of the segment. \item (\textbf{x_2}, \textbf{y_2}) is the point \textbf{Q}, that defines the second extreme of the segment. \end{itemize} You can suppose that neither \textbf{P} nor \textbf{Q} lie in the boundary of any single triangle, and that \textbf{P} ≠ \textbf{Q}. The end of the input is specified by a line with the string "\textbf{0 0 0 0 0 0}". \OutputFile \includegraphics{http://uva.onlinejudge.org/external/116/11662img2.png} For each case in the input, print one line with the number of single triangles on the grid that are intersected by the segment.
Time limit 4 seconds
Memory limit 64 MiB
Input example #1
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
Output example #1
6
1
2
3