울타리
시간 제한2초메모리 제한128 MB
정사각형 농장의 기둥 4N개와 시야를 가리는 최대 30000개의 볼록 다각형 바위가 있을 때, 관찰자의 각도별 가림 구간을 계산해 보이는 기둥 수를 구하는 문제입니다.
문제
농부 장길산은 정사각형 밭을 둘러싼 울타리를 관리한다. 밭의 한 꼭짓점은 (0, 0), 그 맞은편 꼭짓점은 (N, N)이며, 네 변은 x축 또는 y축과 평행하다. 2 <= N <= 500000이다.
울타리 말뚝은 네 꼭짓점과 네 변 위에 1미터 간격으로 박혀 있다. 꼭짓점은 중복해서 세지 않으므로 말뚝은 모두 4N개이다. 말뚝은 두께가 없는 가느다란 선분으로 본다.
밭 안에는 R개의 큰 바위가 있다. 1 <= R <= 30000이다. 각 바위는 밑면과 윗면이 같은 볼록다각형 기둥이며, 충분히 높아서 장길산은 바위 뒤의 말뚝을 볼 수 없다. 바위들의 영역은 서로 겹치지 않고, 꼭짓점이나 변으로 서로 닿지도 않는다. 한 바위가 다른 바위의 안이나 위에 있는 경우도 없다.
밭의 크기, 장길산의 위치, 각 바위의 모양이 주어질 때, 장길산이 제자리에서 고개만 돌려 볼 수 있는 울타리 말뚝의 개수를 구하라. 장길산과 어떤 바위 꼭짓점을 잇는 직선 위에 있는 말뚝은 보이지 않는 것으로 간주한다.
입력
첫째 줄에 N과 R이 주어진다.
둘째 줄에 장길산의 위치 x y가 주어진다.
이후 R개의 바위 정보가 차례로 주어진다. 각 바위 정보의 첫 줄에는 꼭짓점의 개수 p가 주어진다. 3 <= p <= 20이다. 다음 p개의 줄에는 바위를 이루는 꼭짓점의 좌표 x y가 반시계 방향 순서로 주어진다.
모든 꼭짓점 좌표는 서로 다르다. 한 바위의 여러 꼭짓점이 한 직선 위에 있을 수도 있다.
출력
장길산이 현재 위치에서 볼 수 있는 울타리 말뚝의 개수를 한 줄에 출력한다.