Bug2 경로 길이

우리 주변에는 다양한 길찾기 문제가 있습니다. 이 문제는 Bug2라고 불리는 길찾기 알고리즘을 다룹니다.

Bug 계열 알고리즘은 다음과 같은 길찾기 문제를 해결합니다. 임의의 모양을 가진 장애물들이 놓인 2차원 지도와 함께 시작점과 도착점이 주어집니다. 에이전트는 처음에 시작점 S에 서 있으며, 도착점 F에 도달하는 것이 목표입니다. 에이전트는 F의 좌표를 알고 있고, 언제든지 자신의 현재 좌표를 알 수 있습니다. 에이전트의 메모리는 O(1)이므로 장애물 지도를 저장할 수 없습니다. 에이전트가 외부 세계에 대해 얻을 수 있는 유일한 정보는 지금 장애물에 닿아 있는지 여부입니다. 에이전트는 장애물의 경계를 따라 이동할 수 있습니다. 목표는 가능한 경우 F에 도달하고, 불가능한 경우 F에 도달할 수 없다는 사실을 올바르게 보고하는 것입니다.

Bug2 알고리즘은 다음과 같이 동작합니다.

1. 다음 중 하나가 일어날 때까지 F를 향해 직선으로 이동합니다.

   • F에 도달하면 알고리즘을 멈춥니다.
   • 장애물을 만나면 2단계로 갑니다.

2. 현재 점을 H라고 합니다. 다음 중 하나가 일어날 때까지 장애물의 경계를 시계 방향으로 따라 이동합니다.

   • F에 도달하면 알고리즘을 멈춥니다.
   • 점 H에 다시 도달하면 F에 도달할 수 없으므로 알고리즘을 멈춥니다.
   • 직선 SF 위에 있고 |LF| < |HF|를 만족하며, 장애물로 즉시 다시 들어가지 않고 F를 향해 이동할 수 있는 점 L에 도달하면 1단계로 돌아갑니다.

이 알고리즘은 F에 도달할 수 있으면 유한한 시간 안에 반드시 F에 도달하고, 그렇지 않으면 유한한 시간 안에 도달 불가능을 보고함이 증명되어 있습니다.

다각형 장애물들의 집합과 시작점, 도착점이 주어질 때, Bug2 알고리즘을 따르는 에이전트가 지나는 경로의 길이를 구하세요.

첫째 줄에는 다섯 정수 n, xS, yS, xF, yF가 주어집니다. n은 장애물의 개수이고, 나머지는 시작점과 도착점의 좌표입니다.

이후 줄들은 장애물을 설명합니다. 각 장애물의 설명은 정수 m (m ≥ 3)이 적힌 줄로 시작하며, m은 그 장애물의 꼭짓점 개수입니다. 이어지는 m개의 줄에는 각각 두 정수 xi, yi가 시계 방향 순서로 주어지며, 이는 장애물 꼭짓점의 좌표입니다. 각 장애물은 자기교차나 자기접촉이 없는 단순 다각형입니다.

제약 조건:

• 모든 장애물의 꼭짓점 수의 합은 300000을 넘지 않습니다.
• 모든 좌표의 절댓값은 10^6 이하입니다.
• 모든 장애물의 모든 변은 좌표축과 평행합니다(모든 장애물은 직교 다각형입니다).
• 시작점과 도착점의 y좌표가 같습니다. 즉, 선분 SF는 수평입니다.
• 어떤 장애물의 꼭짓점도 직선 SF 위에 있지 않습니다.
• 시작점과 도착점은 모두 모든 장애물의 바깥쪽에 엄격히 위치합니다.
• 어떤 두 장애물도 공통점을 갖지 않습니다.
• 도착점 F는 에이전트가 도달할 수 있습니다.

이 조건들 아래에서 에이전트가 지나는 경로는 정수 좌표를 끝점으로 하는 축과 평행한 선분들로만 이루어집니다.

에이전트가 Bug2 알고리즘을 따라 지나는 경로의 전체 길이를 정수 하나로 출력하세요.

모든 장애물이 직교 다각형이고 선분 SF가 수평이므로, 경로의 모든 구간은 정수 좌표를 끝점으로 하는 축과 평행한 선분입니다. 따라서 전체 길이는 항상 정수입니다. 소수점이나 뒤따르는 0 없이 그 정수를 정확히 출력하세요.