만드는 중입니다

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

센서

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

요약
각 질의마다 원점에서 두 점 사이 시계 방향 부채꼴에 들어가고 원점과의 거리 제곱이 w인 정수 점의 개수를 구합니다.
난이도

보통10점 중 5점

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

문제

QQ개의 쿼리가 주어진다. 각 쿼리는 정수 x1,y1,x2,y2,wx_1, y_1, x_2, y_2, w로 이루어지며, 각 쿼리에 대해 다음 조건을 만족하는 정수 좌표 점의 개수를 구한다.

  • 센서는 원점 (0,0)(0, 0)에 있다. 점 (x1,y1)(x_1, y_1)을 포함하는 각도에서 시작해 시계 방향으로 점 (x2,y2)(x_2, y_2)를 포함하는 각도까지 스캔한다. 이 각도 범위에 포함된 점 중, 센서와의 거리가 w\sqrt{w}인 점을 센다. 세 점 (0,0)(0, 0), (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2)는 일직선상에 있지 않으며, 시계 방향으로 배치되어 있다.

센서의 크기는 무시할 만큼 작으므로 0으로 생각해도 된다. 모든 입력은 정수이다.

입력

첫 번째 줄에 QQ가 주어진다. (1≤Q≤1051 \le Q \le 10^5)

두 번째 줄부터 QQ개의 줄에 걸쳐 각 줄마다 정수 x1,y1,x2,y2,wx_1, y_1, x_2, y_2, w가 차례대로 주어진다. (1≤x1,y1,x2,y2≤1051 \le x_1, y_1, x_2, y_2 \le 10^5; 1≤w≤1051 \le w \le 10^5; 세 점 (0,0)(0, 0), (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2)는 일직선상에 있지 않으며, 시계 방향으로 배치되어 있다.)

출력

각 쿼리를 만족하는 정수 좌표 점의 개수를 QQ개의 줄에 걸쳐 출력한다.

예제1

  1. 예제 1

    입력
    3
1 3 2 1 5
1 1 2 1 5
1 3 1 1 10
    예상 출력
    2
1
1