P1632 Movement of Points

There are $N$ points with integer coordinates on the plane. Moving point $(x_0, y_0)$ to $(x_1, y_1)$ costs $|x_0-x_1|+|y_0-y_1|$. For each $K$ ($K = 1, \cdots, N$), find the minimum total cost to make $K$ points coincide at the same position.

The first line contains a positive integer $N$. The next $N$ lines each contain two positive integers $x_i$ and $y_i$, the coordinates of the $i$-th point, each not exceeding $10^6$. Constraints: For $100\%$ of the testdata, $1 \le N \le 50$.

Output $N$ lines. The $i$-th line is the minimum total cost to make $i$ points coincide at the same position.

Translated by ChatGPT 5