Distance minimization - MarisaOJ: Marisa Online Judge

Distance minimization

Time limit: 1000 ms
Memory limit: 256 MB
Given $n$ points on a 2D coordinate system, each represented by the coordinates $(x_i, y_i)$, the task is to find a point $A$ with integer coordinates such that the sum of distances from $A$ to the given $n$ points is minimized. The distance between point $u$ and point $v$ is $|u_x-v_x|+|u_y-v_y|$. ### Input - The first line contains an integer $n$. - The next $n$ lines, each line contains two integers $x_i,y_i$, a point on the coordinate system. ### Output - An integer representing the minimum sum of distances from $A$ to the given $n$ points. ### Constraints - $1 \le n \le 10^5$. - $|x_i|,|y_i| \le 10^9$. ### Example Input: ``` 4 -1 3 6 -5 4 5 3 4 ``` Output: ``` 19 ```