24522번 - 스네이크 게임

문제

알고리즘 원툴 상원이는 첫 프로젝트를 시작했다. 바로 스네이크 게임을 만드는 것이다.

게임에 자신만의 시그니처를 넣고 싶었던 상원이는 특별한 기능을 추가하기로 했다. 원래 뱀은 초록색이지만 게임을 진행하다가 뱀 모양에 숨겨진 특정 모양인 트리거 패턴이 있다면 뱀의 색을 바꾸는 것이다. 하지만 프로젝트에 며칠 밤을 새운 상원이는 도저히 만들 체력이 없다. 여러분이 힘들어하는 상원이를 위해 기능 구현을 도와주도록 하자. 구현해야 할 기능은 뱀 모양에서 트리거 패턴이 몇 개나 있는지 찾는 것이다.

이때 뱀 모양에 회전된 트리거 패턴도 포함해야 한다. 위 뱀 모양의 경우, 보라색으로 표시된 트리거 패턴은 두 번 나타난다. 단, 회전된 모양과는 다른 뒤집힌 모양인 경우는 포함되지 않음에 유의해야 한다.

뱀 모양과 트리거 패턴이 주어졌을 때, 뱀 모양에 있는 트리거 패턴의 개수를 구해보자.

입력

첫 번째 줄에 뱀 모양을 나타내는 점 개수 $N,ドル 숨겨진 모양을 나타내는 점 개수 $M$이 주어진다. $(3 \le N, M \le 500,000円)$

이어지는 $N$개의 줄에 좌표 $x_i, y_i$가 정수로 주어진다. 뱀 모양은 $(x_i, y_i)$와 $(x_{i+1}, y_{i+1})$을 선분으로 이은 모양이다. $(-10^9 \le x_i, y_i \le 10^9)$

이어지는 $M$개의 줄에 좌표 $x_i, y_i$가 정수로 주어진다. 트리거 패턴은 $(x_i, y_i)$와 $(x_{i+1}, y_{i+1})$을 선분으로 이은 모양이다. $(-10^9 \le x_i, y_i \le 10^9)$

단, 각 모양에 해당하는 선분은 축에 평행하고 연속한 두 선분을 제외하면 서로 겹치지 않는다. 연속한 두 선분은 수직이고 오직 끝 점에서만 만난다.

출력

뱀 모양에 있는 트리거 패턴의 개수를 출력한다.

제한

힌트