dong5995   1년 전

제가 어렵게 푼건지 모르겠어서 많이 푸시고 기여 남겨주시면 좋겠습니다.
지피티 번역입니다

문제

정사각 격자 위에 바나나들이 흩어져 있다. 우리는 바나나를 주워 올 원숭이를 한 마리 가지고 있다. 헬리콥터에서 원숭이를 임의의 칸에 떨어뜨리고, 네 가지 기본 방향(동·서·남·북) 중 하나로 바라보게 할 수 있다. 원숭이는 한 칸 앞으로 이동한 뒤 오른쪽으로 방향을 틀고, 이후에도 계속 그런 식으로 이동하여 그 궤적이 나선(스파이럴) 모양이 되도록 움직인다.

그림은 처음에 위쪽을 바라보게 했을 때 원숭이의 경로의 시작 부분을 보여 준다. 격자는 모든 방향으로 무한히 뻗어 있음을 유의하라.

preview

원숭이를 임의의 칸에 떨어뜨리고 네 방향 중 아무 방향으로나 향하게 할 수 있을 때, 원숭이가 모든 바나나를 줍는 데 필요한 최소 걸음 수를 구하여라. 단, 미끄러져 다치지 않도록 바나나가 놓여 있는 칸에는 원숭이를 떨어뜨릴 수 없다.

입력

첫 줄에는 바나나의 개수 N(1 ≤ N ≤ 100000) 이 주어진다.
다음 N개의 줄에는 각 바나나의 좌표가 주어진다. 좌표는 자연수이며 10^8 미만이다. 한 칸에는 최대 하나의 바나나만 놓일 수 있다.

출력

원숭이가 모든 바나나를 줍는 데 필요한 최소 걸음 수를 자연수 하나로 출력하라.

힌트

예제 입력을 나타낸 그림이다.

preview

댓글을 작성하려면 로그인해야 합니다.