SPC에 가는 길
면접 대비시간 제한1초메모리 제한1024 MB
집, 행사장, 그리고 막힌 한 점이 주어질 때 축에 평행하게 걸어 집에서 행사장까지 가는 최소 방향 전환 횟수를 구합니다.
문제
SPC(Sogang Programming Contest)는 서강대학교 학생 구성원이라면 누구나 참여할 수 있는 프로그래밍 축제이다. 승형이는 오늘 열리는 SPC에 참가하려고 집에서 나와 SPC 대회장으로 가는 중이다.
SPC 대회장과 승형이의 집은 2차원 좌표 평면 위에 있다. 승형이의 집은 , SPC 대회장은 에 있다. 에는 포악한 근수가 자리 잡고 있어 승형이가 지나갈 수 없다. 승형이의 집, 대회장, 근수의 위치는 모두 서로 다르다.
승형이는 축 또는 축에 평행한 방향으로만 직진할 수 있다. 이전까지의 진행 방향과 앞으로의 진행 방향이 다르면 방향 전환이 일어난다. 승형이는 집에서 출발할 때 원하는 방향을 고를 수 있으며, 이때 방향을 고르는 것은 방향 전환 횟수에 포함되지 않는다. 승형이는 어지러움에 약해서, 집에서 출발해 방향 전환 횟수를 최소로 하며 SPC 대회장에 도착하려고 한다. 승형이의 최소 방향 전환 횟수를 구하자.
입력
첫 번째 줄에 승형이의 집을 나타내는 정수 와 가 주어진다.
두 번째 줄에 SPC 대회장을 나타내는 정수 와 가 주어진다.
세 번째 줄에 근수의 위치를 나타내는 정수 와 가 주어진다.
출력
승형이의 최소 방향 전환 횟수를 출력한다.
힌트
승형이가 최단 경로로 SPC 대회장에 도달해야 하는 것은 아니다.