시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 11 4 3 50.000%

문제

이차원 평면상에 변들이 좌표축에 평행한 L-모양 다각형의 장애물들이 있다. 이들 장애물들은 서로 겹치지 않고 또한 변이나 꼭지점에서 만나지 않는다. 로봇이 어느 한 지점에서 출발하여 정해진 도착지점으로 이들 장애물들을 피해서 이동하고자 한다. 이 로봇은 항상 좌표축과 평행하게 이동하며 장애물의 변을 따라서 이동할 수도 있다. 로봇이 출발지점에서 도착지점까지 이동하는 여러 경로들 중에서 꺾이는 횟수가 최소가 되는 경로를 찾고자 한다. 단, 로봇의 크기를 무시하여 로봇을 이차원 상의 점으로 표현할 수 있다고 가정한다. 또한, 로봇의 출발지점과 도착지점은 항상 장애물의 내부나 경계선에 놓여있지 않다.

아래 그림의 예를 통해서 로봇이 도착지점에 도달하기 위한 여러 경로가 있음을 알 수 있고, 또한 이 경우에서는 꺾이는 수가 3이 최소임을 알 수 있다.

L-모양 다각형의 장애물들, 출발지점, 도착지점이 입력으로 주어져 있을 때 로봇이 출발지점에서 도착지점으로 이동하는 경로 중 꺾이는 횟수가 최소인 것을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 로봇의 출발지점 좌표가 주어지고 둘째 줄에는 로봇의 도착지점 좌표가 주어진다. 셋째 줄에는 장애물의 개수(≤50)가 주어지고, 그 다음 줄부터 각 줄에는 하나의 장애물의 위치를 나타내는 네 점의 좌표 p1, p2, p3, p4 가 차례로 주어지고 이 네 점의 좌표의 위치는 다음의 그림과 같다. 단, 모든 좌표는 x-좌표, y-좌표가 한 칸씩 띄어서 순서대로 주어지며, 좌표의 각 값은 자연수(≤100)이다.

출력

로봇의 경로들 중에서 꺾이는 횟수가 최소가 되는 경로의 꺾이는 횟수를 출력한다.

예제 입력

3 6
10 6
4
8 4 8 2 11 2 9 3
4 5 2 5 2 2 3 3
7 4 7 9 2 9 5 8
11 8 8 8 8 5 9 7

예제 출력

3

힌트