DSHS Bank
면접 대비시간 제한2초메모리 제한512 MB
모든 지점까지 택시 거리 합이 가장 작은 지점을 고르고 거리 합이 같으면 번호가 가장 작은 지점을 출력합니다.
문제
대구과학고등학교를 대표하는 은행인 Park Bank는 올해 2월을 마지막으로 문을 닫았다. 이번에는 작년에 이 은행에서 제기되었던 문제 중 하나를 가져왔다.
꾸준히 성장하던 Park Bank는 전성기에 총 N개의 지점을 가지게 되었다. 각 지점은 2차원 평면 위의 어떤 좌표에 있다. 아직 "본점"이 없었던 Park Bank는 효율적인 관리를 위해 N개 지점 중 하나를 본점으로 정하려 한다. 본점은 다른 모든 지점과의 택시 거리의 합이 최소가 되어야 한다. 어느 지점이 본점이 되어야 하는지 구하는 프로그램을 작성하시오. 답이 여러 개라면 번호가 가장 작은 지점의 번호를 출력한다.
입력
첫째 줄에는 은행 지점의 개수(본점이 될 하나의 지점을 포함한 개수이다.) N이 주어진다. (2 ≤ N ≤ 500,000)
그 뒤의 N개 줄에는 1번부터 N번까지 번호가 붙은 각 지점의 좌표를 나타내는 두 정수 xi, yi가 차례로 주어진다. 각 좌표의 절댓값은 109 이하이다. 서로 같은 좌표가 여럿 있을 수 있음에 유의하라.
출력
본점이 되어야 할, 즉 다른 지점들과의 택시 거리의 합이 가장 작은(그런 지점이 여러 개이면 가장 번호가 작은) 지점의 번호를 나타내는 정수 하나를 출력한다. 지점의 번호가 1번부터 시작함에 유의하라.
힌트
두 점 (x1, y1)와 (x2, y2) 사이의 택시 거리는 |x1-x2|+|y1-y2| (| |는 절댓값 기호이다)로 정의된다.