시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 6 2 1 100.000%

문제

농부 장길산은 자신의 밭을 감싸는 울타리를 관리하고 있다. 밭은 가로 세로 N미터인 정사각형 평지이다. (2<=N<=500000) 밭 경계의 한쪽 끝 좌표는 (0, 0)이며, 맞은편 끝 좌표는 (N, N)이다. 또한 경계는 x, y 축에 평행하다.

울타리를 나타내는 말뚝은 일단 밭의 네 모서리에 박혀 있고, 그 사이 네 변 구간에도 1미터 간격으로 박혀 있다. 따라서 말뚝은 총 4N개가 있다. 이 문제에서 말뚝은 땅 위로 솟아 있는 홀쭉한 선분이며 반지름, 즉 굵기가 없다고 가정한다. 길산은 밭 안 어느 위치에 서서 사방을 돌아볼 때, 거기서 밭의 끝 경계에 있는 말뚝을 몇 개까지 볼 수 있나 알고 싶어 한다.

그의 밭 안에는 R (1<=R<=30000)개의 커다란 바위가 있어서 그의 시야를 일부 가린다. 바위는 밑면과 윗면이 같은 볼록다각형으로 구성된 기둥이며, 높이가 충분히 높기 때문에 길산은 바위 너머로 있는 말뚝을 볼 수 없다. 바위들은 영역이 서로 겹치지 않으며, 꼭지점이나 선분이 접하지도 않는다. 한 바위가 다른 바위 안이나 위에 있지도 않다.
길산이 가진 밭(울타리)의 크기, 길산이 밭 안에 있는 위치, 그리고 각 바위들에 대한 정보가 들어왔을 때, 그가 그 위치에서 고개만 돌려서 볼 수 있는 울타리 말뚝의 총 개수를 계산하는 프로그램을 작성하시오. 바위를 구성하는 임의의 한 정점과 농부와 일직선을 이루는 말뚝은 농부에게 보이지 않는다.

입력

첫 줄에는 N과 R의 값이 순서대로 들어있다. 다음 줄에는 장길산의 x, y 위치가 순서대로 들어있다. 그리고 다음 줄에는 R개의 바위에 대한 정보가 순서대로 들어온다.
  바위에 대한 정보는 다각형을 기술하는 것과 같으므로, 가장 먼저 이 바위의 꼭지점 개수를 나타내는 p가 있다. (3<=p<=20) 그리고 다음 p 줄에는 다각형을 구성하는 x y 좌표가 순서대로 들어온다. 꼭지점의 좌표들은 모두 서로 값이 다르며 반시계 방향이다.
  아래 예제의 (70, 40), (75, 40), (80, 40)처럼, 정점 좌표가 일직선 상에 있는 경우도 있을 수 있다.

출력

길산이 그 위치에서 볼수 있는 말뚝의 개수를 한 줄에다 출력하면 된다. 아래의 예제를 살펴보면, 농부는 (60, 50) 위치에 있는데 (70, 40) 위치의 바위 꼭지점 때문에 (100, 10)부터. 또 (70, 60) 위치의 바위 꼭지점 때문에 (100, 90)까지, 경계에 있는 81개의 말뚝이보이지 않게 된다. 따라서 정답은 400에서 81을 뺀 319이다.

예제 입력

100 1
60 50
5
70 40
75 40
80 40
80 50
70 60

예제 출력

319

힌트