### 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)**.