Processing math: 100%
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 (xi,yi), 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 |ux−vx|+|uy−vy|. ### Input - The first line contains an integer n. - The next n lines, each line contains two integers xi,yi, a point on the coordinate system. ### Output - An integer representing the minimum sum of distances from A to the given n points. ### Constraints - 1≤n≤105. - |xi|,|yi|≤109. ### Example Input: 4-136-54534 Output: 19