Kejriwal and Internet (Easy-medium)
All submissions for this problem are available.
Mr Kejriwal recently became the CM of delhi. So as promissed, he has decided to make complete capital Internet connected with optical fiber connectivity. He treats the capital as a Cartesian plane where each block in the cartesean plane represents a house.
He places a optical fiber between point (x1,y1) and point (x2,y2).
the fiber is a straight line from (x1,y1) to (x2,y2) and the fiber is only contained within these two points.
All the blocks in the 2d XY plane that are are cut by this line are provided internet connectivity.
Your task is to evaluate the number of blocks which have internet connectivity.
The first line contains single integer T, the number of test cases. For every test case T there are four space separated integers for x1,x2,y1 and y2.
For every test case you have to print the number of blocks or cells in the 2d xy plane that are cut by the line segment of the optical fiber. Remember that a block/cell is considered to be cut by the line if and only if the line enters the block/cell, only touching a side is not enough.
- 0 < T < 100
- 0 ≤ x1,x2,y1,y2 ≤ 1000000000.
Input: 3 0 3 0 2 0 2 0 2 0 1 0 0 Output: 4 2 0
In the first case the line segment between points (0,0) and (3,2) cuts
4 blocks.It enters the block with left botton corner (0,0) directly and then cuts the block on its right having (1,0) left bottom corner. After that it cuts the block on top with (1,1) as the left bottom corner and lastly cuts the block with (2,1) as left bottom corner and then the line segment terminates at (3,2).
In the second case the line segment between points (0,0) and (2,2) starts at (0,0) and cuts the block with (0,0) at left bottom corner first. The line segment does not enter the blocks with left bottom corners at (0,1) and (1,0). Then it lastly enters the block with left bottom corner (1,1).So only 2 blocks are cut.
In the third case the line segment does not cut through any block hence the answer is 0.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PHP|
Fetching successful submissions
If you are still having problems, see a sample solution here.