For a given point (x1, y1), it is necessary to find the closest point to it (x2, y2). The are four cases:

1. x2 >= x1 and y2 >= y1

2. x2 >= x1 and y2 <= y1

3. x2 <= x1 and y2 >= y1

4. x2 <= x1 ans y2 <= y1

Let's see how to solve the case #1.

Since x2 >= x1 and y2 >= y1, then dist(p1, p2) = |x2 — x1| + |y2 — y1| = x2 — x1 + y2 — y1 = (x2 + y2) — (x1 + y1).

As you can see, the best option in this case is to choose the point such that x2 + y2 is minimum. This can be solved using a data structure supporting the following two functions:

query(Y): finds the point (x, y) such that y >= Y and x + y is minimum among all the points in the structure.

add((x, y)): adds the point (x, y) to the structure.

An example of such data structure is a Binary Indexed Tree.

Let p be the input points:

sort p in decreasing order of x coordinates

foreach point in p
    answer[point] = query(point.y)
    add(point)

The other three cases can be solved in a similar way.