시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 147 27 24 43.636%

문제

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

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

입력

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

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

출력

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

서브태스크 1 (12점)

N≤5,000을 만족한다.

서브태스크 2 (19점)

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

서브태스크 3 (19점)

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

예제 입력 1

4
1 1
2 4
3 2
5 1

예제 출력 1

3

힌트

두 점 (x1, y1)와 (x2, y2) 사이의 택시 거리는 |x1-x2|+|y1-y2| (| |는 절댓값 기호이다)로 정의된다.

출처

High School > 대구과학고등학교 > 대구과학고 코드잼 경시대회 2018 3번

  • 데이터를 만든 사람: daun20211
  • 문제를 만든 사람: junie

채점

  • 예제는 채점하지 않는다.