센서

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

요약
각 쿼리마다 원점에서의 거리가 sqrt(w)이고 주어진 시계방향 스캔 각도 범위에 들어가는 정수 좌표 점의 개수를 센다.
난이도

어려움10점 중 8점

유형
수학, 정수론, 기하, 이분 탐색
정답자
아직 제출이 없습니다

문제

다음과 같은 형태의 쿼리 QQ개가 주어질 때, 각 쿼리에 대해 조건을 만족하는 정수 좌표 점의 개수를 출력하라.

  • x_1,y_1,x_2,y_2,wx\_1, y\_1, x\_2, y\_2, w: 센서가 존재하는 원점 (0,0)(0, 0)을 기준으로, 점 (x_1,y_1)(x\_1, y\_1)를 포함하는 각도부터 시계방향으로 점 (x_2,y_2)(x\_2, y\_2)를 포함하는 각도까지를 센서에서 스캔했을 때, 해당 각도에 포함된 점들 중 센서와의 거리가 w\sqrt{w}여야 한다. (단, 세 점 (0,0),(x_1,y_1),(x_2,y_2)(0, 0),(x\_1, y\_1),(x\_2, y\_2)은 일직선상에 있지 않으며, 시계방향으로 배치되어있다.)

센서의 크기는 무시해도 될 정도로 작다. 즉, 00으로 생각해도 무방하다. 모든 입력은 정수이다.

입력

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

두 번째 줄부터 QQ개의 줄에 걸쳐 각 줄마다 정수 x_1,y_1,x_2,y_2,wx\_1, y\_1, x\_2, y\_2, w가 차례대로 주어진다. (1≤x_1,y_1,x_2,y_2≤105;(1 \le x\_1, y\_1, x\_2, y\_2 \le 10^5; 1≤w≤105;1 \le w \le 10^5; 세 점 (0,0),(x_1,y_1),(x_2,y_2)(0, 0),(x\_1, y\_1),(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