16210번 - DSHS Bank 서브태스크

대구과학고등학교를 대표하는 은행인 Park Bank는 올해 2월을 마지막으로 문을 닫았다. 이번에는 작년에 이 은행에서 제기되었던 문제 중 하나를 가져왔다.

꾸준히 성장하고 있었던 Park Bank는 전성기에 총 N개의 지점을 가지게 되었다. 각 지점은 2차원 평면 상의 어떤 좌표 위에 존재한다. 아직까지 "본점"이 없었던 Park Bank는 효율적인 관리를 위해 N개 지점 중 하나를 본점으로 정하려 한다. 본점은 다른 모든 지점과의 택시 거리의 합이 최소가 되어야 한다. 몇 번 지점이 본점이 되어야 할 지를 구하는 프로그램을 작성하시오. 답이 여러 개가 될 수 있다면 번호가 가장 작은 지점의 번호를 출력하면 된다.

첫째 줄에는 은행의 지점의 개수(본점이 될 하나의 지점을 포함한 개수이다.) N이 주어진다. (2 ≤ N ≤ 500,000)

그 뒤의 N개의 줄에는 1번부터 N번으로 번호가 붙여진 각 지점의 좌표를 나타내는 두 정수 x_i, y_i가 차례로 주어진다. 각 좌표의 절댓값은 10⁹ 이하이다. 서로 같은 좌표가 여럿 있을 수 있음에 유의하라.

본점이 되어야 할, 즉 다른 지점들과의 택시 거리의 합이 가장 작은(그런 정점이 여러 개이면 가장 번호가 작은) 지점의 번호를 나타내는 정수 하나를 출력한다. 지점의 번호가 1번부터 시작함에 유의하라.

N ≤ 5,000을 만족한다.

모든 지점의 y좌표는 0이다.

문제에 제시된 조건 이외의 다른 제약은 없다.

두 점 (x₁, y₁)와 (x₂, y₂) 사이의 택시 거리는 |x₁-x₂|+|y₁-y₂| (| |는 절댓값 기호이다)로 정의된다.