Computing the number of squares which are intersected by a line internally - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-20T03:21:18Z https://cs.stackexchange.com/feeds/question/44517 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/44517 -1 Computing the number of squares which are intersected by a line internally Abhishek Karmakar https://cs.stackexchange.com/users/35632 2015-07-18T21:02:18Z 2015-07-18T22:11:24Z <p>There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only touched by the line should not be counted. Notes x1,y1,x2,y2 are all integers. 0 &lt;= x1,y1,x2,y2 &lt;= 10000 Write the program so that it accepts 4 command line parameters - x1,y1,x2,y2 The output of the program should be a single line consisting of only the integer output Example: Input (x1 y1 x2 y2): 1 1 6 6 Output (No. of squares): 5</p> <p><img src="https://i.stack.imgur.com/KJYxS.png" alt="Here is the image description of generated squres"></p> <p>please help me to understand how these squares will generate? do i need to predefined all the squares in a 2d matrix form?</p> https://cs.stackexchange.com/questions/44517/-/44518#44518 1 Answer by Ran G. for Computing the number of squares which are intersected by a line internally Ran G. https://cs.stackexchange.com/users/157 2015-07-18T21:28:59Z 2015-07-18T21:28:59Z <p>As the question says, the program should be as follows:</p> <h3>INPUT:</h3> <p>4 integer numbers: \$(x_1,y_1)\$, \$(x_2,y_2)\$</p> <h3>OUTPUT:</h3> <p>a single number \$n\$. </p> <p>\$n\$ should be the number of squares that are touched by a line that starts at \$(x_1,y_1)\$ and ends at \$(x_2,y_2)\$. Assuming the squares are of length 1, and the first square has corners at (0,0), (1,0), (0,1), (1,1).</p> <p>That's it. Nobody gives you the squares as a matrix or any other form. They are not in the memory, and nobody tells you how to construct them. Furthermore, your program DOES NOT NEED to construct the squares. It can, but it needs not. The output \$n\$ can be found in a purely mathematical way.</p>