만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

건축가

시간 제한1초메모리 제한64 MB

요약
N개의 나무 좌표와 꼭짓점이 12개 이하인 Q개의 축 정렬 다각형이 주어질 때, 각 다각형 내부(경계 포함)에 있는 나무의 수를 센다.
난이도

보통10점 중 6점

유형
기하, 배열, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

마티야는 주택을 짓는 회사에 취직했다. 매일 여러 고객이 특정 필지에 건물을 올리고 싶다며 주문을 넣는다. 마티야가 할 일은 그 필지 안에 있는 나무를 모두 베는 것이다. 주문을 다 모으면 먼저 필지마다 그 안에 나무가 몇 그루 있는지 세야 한다. 아직 아무것도 베지 않은 현재 상태를 기준으로 세고, 필지 경계선 위에 있는 나무도 안에 있는 것으로 센다.

평면에 놓인 모든 나무의 위치와 고객이 관심을 둔 필지의 정보가 주어진다. 나무 한 그루의 크기는 무시한다. 각 필지는 꼭짓점이 KK개인 다각형이고, 모든 변은 가로 또는 세로다. 한 필지의 변끼리는 절대 서로 만나지 않지만, 서로 다른 필지는 겹칠 수 있다.

입력

첫째 줄에 평면에 있는 나무의 수 NN이 주어진다 (1≤N≤100 0001 \le N \le 100\,000). 다음 NN개의 줄에는 나무 한 그루의 좌표를 나타내는 정수 XX, YY가 주어진다 (∣X∣,∣Y∣≤100 000|X|, |Y| \le 100\,000). 좌표가 같은 나무는 없다.

다음 줄에 고객 주문의 수 QQ가 주어진다 (1≤Q≤1 0001 \le Q \le 1\,000). 이어서 주문을 설명하는 2Q2Q개의 줄이 온다. 주문 하나는 두 줄로 이루어진다. 첫 줄에는 필지를 나타내는 다각형의 꼭짓점 수 KK가 주어지고 (4≤K≤124 \le K \le 12), 둘째 줄에는 그 필지의 꼭짓점 좌표를 순서대로 짝지어 나열한 정수 2K2K개가 주어진다. 필지 꼭짓점의 좌표도 절댓값이 100 000100\,000 이하다.

꼭짓점은 반시계 방향으로 주어진다. 이웃한 두 변은 항상 하나가 가로, 다른 하나가 세로다.

출력

QQ개의 줄을 출력한다. 고객 주문마다 해당 필지에 있는 나무의 수를 한 줄에 하나씩 출력한다. 출력의 AA번째 줄은 입력의 AA번째 주문에 대응해야 한다.

예제3

  1. 예제 1

    입력
    1
    -100 -100
    2
    4
    0 0 100 0 100 1 0 1
    4
    0 0 1 0 1 100 0 100
    
    예상 출력
    0
    0
    
  2. 예제 2

    입력
    4
    1 1
    2 2
    3 3
    4 4
    2
    4
    1 1 2 1 2 2 1 2
    4
    -5 -5 5 -5 5 5 -5 5
    
    예상 출력
    2
    4
    
  3. 예제 3

    입력
    8
    1 1
    1 2
    1 3
    2 1
    2 3
    3 1
    3 2
    3 3
    1
    6
    1 1 3 1 3 2 2 2 2 3 1 3
    
    예상 출력
    7