농부 창호는 자신의 밭을 감싸는 울타리를 관리하고 있다.

밭은 가로 세로 N미터인 정사각형 평지이다. (2≤N≤500,000)

밭 경계의 한쪽 끝 좌표는 (0, 0)이며, 맞은편 끝 좌표는 (N, N)이다. 또한 경계는 x, y 축에 평행하다.

울타리를 나타내는 말뚝은 일단 밭의 네 모서리에 박혀 있고, 그 사이 네 변 구간에도 1미터 간격으로 박혀 있다.

따라서 말뚝은 총 4N개가 있다. 이 문제에서 말뚝은 땅 위로 솟아 있는 홀쭉한 선분이며 반지름, 즉 굵기가 없다고 가정한다.

창호는 밭 안 어느 위치에 서서 사방을 돌아볼 때, 거기서 밭의 끝 경계에 있는 말뚝을 몇 개까지 볼 수 있나 알고 싶어 한다.

그의 밭 안에는 R (1≤R≤30,000)개의 커다란 바위가 있어서 그의 시야를 일부 가린다.

바위는 밑면과 윗면이 같은 볼록다각형으로 구성된 기둥이며,

높이가 충분히 높기 때문에 창호는 바위 너머로 있는 말뚝을 볼 수 없다.

바위들은 영역이 서로 겹치지 않으며, 꼭짓점이나 선분이 접하지도 않는다.

한 바위가 다른 바위 안이나 위에 있지도 않다.

창호가 가진 밭(울타리)의 크기, 창호가 밭 안에 있는 위치, 그리고 각 바위들에 대한 정보가 들어왔을 때,

그가 그 위치에서 고개만 돌려서 볼 수 있는 울타리 말뚝의 총 개수를 계산하는 프로그램을 작성하시오.

바위를 구성하는 임의의 한 정점과 농부와 일직선을 이루는 말뚝은 농부에게 보이지 않는다.

울타리2 timer 1s memory 256MB

울타리2 1s 256MB