32195번 - 야구

문제

야구장의 담장은 원의 1/4을 이루는 원주 형태로, 2차원 좌표 평면 상에서 중심이 원점인 원의 방정식 $x^2 + y^2 = R^2$ 으로 주어진다. 여기서 $R$은 담장까지의 거리이다. 담장의 범위는 동경 45ドル^\circ$에서 135ドル^\circ$에 해당한다.

다시 말해, 담장은 다음의 부등식을 만족하는 동시에 $x^2 + y^2 = R^2$을 만족하는 점들로 구성된다:

$ y \geq x$ 및 $y \geq -x $

타구의 위치에 따라 다음과 같이 분류된다:

• 내야: 타구가 담장의 부채꼴 영역 내부(경계 포함)에 위치.
• 홈런: 타구가 담장 바깥에 위치하며, 홈 플레이트 (좌표 평면의 원점) 와 타구의 위치를 잇는 선분이 담장과 교차함.
• 파울: 그 외의 경우.

LG 트윈스와 두산 베어스는 잠실 야구장을 홈구장으로 사용한다. 이들이 더 나은 환경에서 경기하기 위해 잠실 야구장을 돔구장의 형태로 재건축할 계획이다. 재건축 계획의 핵심은 담장까지의 거리를 정하는 것이다. 구단은 담장까지의 거리로 $Q$개의 후보 $R_1, \cdots, R_Q$를 생각하고 있다.

여러 개의 타구의 위치가 주어질 때, 담장까지 거리의 각 경우에 대해 파울, 내야, 홈런의 개수를 계산하라.

입력

첫 줄에 전체 타구의 개수 $N$이 주어진다.

다음 $N$개의 줄에 걸쳐, $i$ (1ドル \le i \le N$)번째 줄에 각 타구가 떨어진 지점 $x_i$와 $y_i$가 사이에 공백을 두고 주어진다.

다음 줄에 '담장까지의 거리'의 후보의 수 $Q$가 주어진다.

다음 $Q$개의 줄에 걸쳐, $i$ (1ドル \le i \le Q$)번째 줄에 담장까지의 거리로 고려되는 $i$번째 후보 $R_i$가 주어진다.

출력

$i$번째 줄 (1ドル \le i \le Q$)에는, 담장까지의 거리가 $R_i$일 때 파울 타구의 수, 내야 타구의 수, 홈런의 수를 공백으로 구분하여 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル \le N \le 300,000円$
• $-10^9 \le x_i \le 10^9$ (1ドル \le i \le N$)
• $-10^9 \le y_i \le 10^9$ (1ドル \le i \le N$)
• 1ドル \le Q \le 300,000円$
• 1ドル \le R_i \le 10^9$ (1ドル \le i \le Q$)

노트

충분히 빠른 입출력 방식을 사용하지 않으면 시간 초과를 받을 수 있다. 예를 들면, C++의 cin/cout을 사용할 때에는 입력받기 전에 cin.tie(NULL);을 사용하고, python에서는 input() 대신 sys.stdin.readline()을 사용하는 것을 권장한다.