z-dots
You are given a set S of N points on a plane. The points have integer coordinates. For each of the points we define a function
d(A) = sum(B in S) max {| Ax - Bx |, | Ay - By |}
Find a point for which this function has the lowest value.
InputThe input is given on the standard input. In the first line an integerN is given, 1 <= N <= 100.000, N represents the number of points in the plane. In the following N lines there are two integers from the range [-10000, 10000] separated by a space, representing the coordinates of each of the points.
OutputTo the standard output write one integer representing the index of the point which has the lowest value for the defined function. If there is more than one point with the same lowest value, then output the index of the one with the lower index.
The indices of the points are from the segment 0 to N - 1
Input:
Output:
3
0 0
1 1
3 0Output:
1 Explanation: For this test we have the following values for the defined function::
d(0) = 0 + 1 + 3 = 4
d(1) = 1 + 0 + 2 = 3
d(3) = 3 + 2 + 0 = 5
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.