아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

과녁 맞히기

면접 대비

시간 제한2초메모리 제한256 MB

요약
최대 30개의 직사각형과 원 표적에 대해 최대 100개의 사격점마다 경계를 포함해 속한 표적 개수를 셉니다.
난이도

쉬움10점 중 2점

유형
기하, 구현
정답자
아직 제출이 없습니다

문제

계산 기하의 기본 연산 중 하나는 두 물체가 서로 닿는지 판정하는 것이다. 예를 들어 무언가를 쏘는 게임에서는 플레이어가 쏜 탄이 과녁을 맞혔는지 판정해야 한다. 탄은 평면 위의 점 하나이고, 과녁은 평면 위의 닫힌 영역이다. 탄이 과녁 안에 있으면 그 과녁을 맞힌 것이다. 과녁의 경계도 과녁 안에 포함된다.

과녁끼리 겹칠 수 있으므로, 탄 하나가 몇 개의 과녁을 맞혔는지 세어야 한다.

입력

첫 줄에 과녁의 개수 mm이 주어진다 (1≤m≤301 \le m \le 30).

다음 mm개의 줄은 각각 rectangle 또는 circle로 시작하고, 그 뒤에 과녁의 경계가 이어진다.

직사각형 과녁의 경계는 네 정수 x1x_1 y1y_1 x2x_2 y2y_2로 주어지며, x1<x2x_1 < x_2이고 y1<y2y_1 < y_2이다. 점 (x1,y1)(x_1, y_1)은 직사각형의 왼쪽 아래 꼭짓점, 점 (x2,y2)(x_2, y_2)는 오른쪽 위 꼭짓점이다.

원형 과녁의 경계는 세 정수 xx yy rr로 주어진다. 원의 중심은 (x,y)(x, y)이고 반지름 rr은 0<r≤10000 < r \le 1000을 만족한다.

과녁 설명 다음 줄에는 탄의 개수 nn이 주어진다 (1≤n≤1001 \le n \le 100). 이어지는 nn개의 줄에는 각각 탄의 좌표 xx yy가 정수로 주어진다.

과녁과 탄의 모든 xx, yy 좌표는 −1000-1000 이상 10001000 이하의 정수이다.

출력

nn개의 탄 각각에 대해 그 탄이 맞힌 과녁의 개수를 한 줄에 하나씩 순서대로 출력한다.

예제5

  1. 예제 1

    입력
    3
    rectangle 1 1 10 5
    circle 5 0 8
    rectangle -5 3 5 8
    5
    1 1
    4 5
    10 10
    -10 -1
    4 -3
    
    예상 출력
    2
    3
    0
    0
    1
    
  2. 예제 2

    입력
    2
    circle 0 0 5
    rectangle -3 -3 3 3
    6
    3 4
    4 3
    5 0
    0 5
    3 3
    -3 -4
    
    예상 출력
    1
    1
    1
    1
    2
    1
    
  3. 예제 3

    입력
    1
    circle 0 0 1
    1
    0 0
    
    예상 출력
    1
    
  4. 예제 4

    입력
    2
    circle 0 0 1
    rectangle 5 5 6 6
    3
    1 1
    4 5
    -2 0
    
    예상 출력
    0
    0
    0
    
  5. 예제 5

    입력
    3
    circle 0 0 3
    rectangle -2 -2 2 2
    rectangle -1000 -1000 -999 -999
    6
    2 2
    3 1
    0 3
    -3 0
    2 -2
    -1000 -1000
    
    예상 출력
    2
    0
    1
    1
    2
    1