PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM
PRE-REQUISITES:
Geometry, Maths
PROBLEM:
Consider a K x K square matrix made of unit squares (K<10000). The center of the lowermost, leftmost unit square has coordinates (0, 0) and the center of the rightmost, uppermost unit square has coordinates ((K-1), (K-1)). If the robot starts from the center (a,b) of a unit square to retrieve an object from the center (c,d) of another unit square, what is the number of unit squares it has to pass through? Note that touching any boundary point on a unit square also counts as passing through that unit square.
EXPLANATION:
We we traverse through all the columns. Each column is defined by two lines x=i+0.5 and x=i+1.5. Since we know equation of our lines, we know at which two points the given line define by points (a,b) and (c,d) intersects the boundary of the columns.
To find these intersection points, find equation of line and then put values of x in equations to get y1 and y2.
See, the following image:
Cells marked blue need to be counted to answer. For each column if y1 is a apparent-lattice point(ie. point touching 4 cells), we need to increment the answer by 1. Similarly for y2.
Also, we’ll need to add to answer ceil(y2)-floor(y1) to count the number of cells it passes through.
For first column and the last column, we’ll separately count the number of touched cells by the above formula.
Complexity: O(K).