로봇

이차원 평면에 좌표축과 평행한 변만 가진 L자 모양 장애물들이 놓여 있다. 장애물들은 서로 겹치지 않으며, 변이나 꼭짓점에서도 서로 만나지 않는다.

로봇은 한 출발점에서 정해진 도착점까지 장애물을 피해 이동하려고 한다. 로봇은 항상 좌표축과 평행한 방향으로만 이동할 수 있으며, 장애물의 변을 따라 이동하는 것은 허용된다. 로봇의 크기는 무시할 수 있어서 평면 위의 한 점으로 생각한다. 출발점과 도착점은 항상 장애물의 내부나 경계 위에 있지 않다.

다음 그림은 도착점까지 갈 수 있는 여러 경로가 있음을 보여 주며, 이 경우 가능한 경로 중 꺾이는 횟수의 최솟값은 3이다.

L자 모양 장애물들, 출발점, 도착점이 주어질 때, 출발점에서 도착점으로 가는 경로 중 꺾이는 횟수의 최솟값을 구하시오.

첫째 줄에 로봇의 출발점 좌표가 주어진다. 둘째 줄에 로봇의 도착점 좌표가 주어진다. 셋째 줄에 장애물의 개수 (N)이 주어지며, (N \le 50)이다.

이후 (N)개의 줄에는 각 장애물의 위치를 나타내는 네 점 (p_1, p_2, p_3, p_4)의 좌표가 차례로 주어진다. 각 점은 x y 형식으로 주어지므로 한 장애물은 정수 8개로 표현된다. 네 점의 위치 관계는 다음 그림과 같다.

모든 좌표값은 100 이하의 자연수이다.

출발점에서 도착점까지 이동하는 경로 중 꺾이는 횟수가 최소인 경로의 꺾이는 횟수를 출력한다.