### PROBLEM LINK:

**Author:** Konstantsin Sokol

**Tester:** Gedi Zheng

**Editorialist:** Miguel Oliveira

### DIFFICULTY:

Medium.

### PREREQUISITES:

Geometry, Manhattan distance.

### PROBLEM

Given a set of **N** points and constants **a** and **b**, calculate the sum of the distances between each pair of points. However, the distance between 2 points is defined as max(a × |x1 - x2|, b × |y1 - y2|).

### QUICK EXPLANATION

- Transform each coordinate (x, y) into (\frac{a * x + b * y}{2}, \frac{a * x - b * y}{2}).
- Calculate the distance between all pairs of points using the Manhattan distance on the new coordinates.

### EXPLANATION

Problem MOSTDIST, required a transformation from Manhattan distance metric to maximum metric (editorial here). Here, we do the reverse. Suppose a = b = 1. Then the distance between points **A** and **P** is max(|A_x - P_x| , |A_y - P_y|).

max(|A_x - P_x| , |A_y - P_y|) = max(A_x - P_x , P_x - A_x , A_y - P_y , P_y - A_y)

Let’s perform the following variable transformation

\begin{cases} A_x = S_x + S_y \\ A_y = S_x - S_y \\ P_x = T_x + T_y \\ P_y = T_x - T_y \end{cases}

We get

max( Ax - Px , Px - Ax , Ay - Py , Py - Ay ) =

max( (Sx+Sy) - (Tx+Ty), (Tx+Ty) - (Sx+Sy), (Sx-Sy) - (Tx-Ty), (Tx-Ty) - (Sx-Sy) )

Rearrange this into

max( (Sx-Tx) + (Sy-Ty), (Tx-Sx) + (Ty-Sy), (Sx-Tx) + (Sy-Ty), (Tx-Sx) + (Ty-Sy) ) =

max( Sx - Tx , Tx - Sx ) + max( Sy - Ty , Ty - Sy ) =

|Sx-Tx| + |Sy-Ty|

So we were able to get rid of the maximum function and only have a manhattan distance on these 4 variables. Inverting the transformation, we have

\begin{cases} S_x = \frac{A_x + A_y}{2} \\ S_y = \frac{A_x - A_y}{2} \\ T_x = \frac{P_x + P_y}{2} \\ T_y = \frac{P_x - P_y}{2} \end{cases}

Hence, we can modify the given point coordinates using this transformation and then calculate the manhattan distance between all the points using the new coordinate system.

In order to take the parameters **a** and **b** into account, we can just multiply each variable in **x** by **a** and each variable in **y** by **b**.

Note that we can avoid using floating point numbers in the coordinates due to division by 2 by using the transformations new_x = x + y, new_y = x - y and divide the result by 2 in the end.

**Time Complexity**

We sort the coordinates and then process them in linear time. Hence, the total time complexity is O(N log N).