머나먼 땅에 하나의 요새가 있습니다. 데카르트 좌표계를 사용하여 방향을 나타내면, 요새의 영역은 원점을 중심으로 하고 반지름이 $R$인 원으로 볼 수 있습니다. 요새 영역의 경계는 높은 성벽으로 둘러싸여 있어서, 요새 내부에서는 바깥을 볼 수 없습니다.
요새 내부에는 몇 개의 건물이 있습니다. 편의상 건물들의 경계는 각 변이 좌표축에 평행하고 서로 겹칠 수도 있는 $n$개의 직사각형으로 나타냅니다. 요새 내부의 한 점이 어떤 직사각형의 내부에 엄밀하게 포함되면 그 점은 가려진 것으로 간주합니다(직사각형의 경계 위에 있는 점은 내부에 있는 것으로 간주하지 않습니다).
Little S는 이 요새의 경비병입니다. 그는 요새 내부의 가려지지 않은 어떤 점 $(x, y)$에 서 있습니다. Little S가 요새 내부의 다른 점 $(x', y')$을 경비할 수 있다는 것은 선분 $(x, y) - (x', y')$ 위의 모든 점(양 끝점 포함)이 가려지지 않았음을 의미합니다. 여러분의 과제는 Little S가 경비할 수 있는 점들의 집합의 넓이, 즉 Little S가 감시할 수 있는 요새 부지의 넓이를 계산하는 것입니다.
입력
이 문제는 여러 개의 테스트 케이스로 이루어져 있습니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다.
각 테스트 케이스에 대하여:
- 첫 번째 줄에는 요새의 반지름과 직사각형의 개수를 나타내는 두 정수 $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$)이 주어집니다.
- 다음 $n$개의 줄에는 각각 직사각형을 설명하는 네 정수 $x_1, y_1, x_2, y_2$ ($|x_1|, |x_2|, |y_1|, |y_2| \le 10^6, x_1 < x_2, y_1 < y_2$)가 주어지며, 여기서 $(x_1, y_1)$은 왼쪽 아래 꼭짓점의 좌표를, $(x_2, y_2)$는 오른쪽 위 꼭짓점의 좌표를 나타냅니다. 모든 직사각형은 요새 영역 내부에 엄밀하게 포함되며 영역의 경계와 닿지 않음이 보장됩니다.
- 마지막 줄에는 Little S의 좌표를 나타내는 두 정수 $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$)가 주어집니다. 점 $(x, y)$는 가려지지 않았음이 보장됩니다.
모든 테스트 케이스에서 $n$의 합은 $10^5$을 넘지 않음이 보장됩니다.
출력
각 테스트 케이스마다 한 줄에 Little S가 요새 안에서 경비할 수 있는 점들의 집합의 넓이를 나타내는 실수를 출력합니다.
정답과의 상대 오차 또는 절대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다. 즉, 여러분의 출력이 $a$이고 정답이 $b$일 때, $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$를 만족하면 정답으로 간주합니다.
예제
입력
2 2 3 -1 -1 0 0 -1 -1 0 1 0 -1 1 0 1 1 26 5 -3 -23 10 21 -15 3 -5 14 -12 -18 -10 -15 -5 -6 -2 8 7 -23 10 -19 -10 0
출력
5.598332050807308 513.142778328943998
노트
첫 번째 테스트 케이스에 해당하는 그림은 다음과 같습니다:
두 번째 테스트 케이스에 해당하는 그림은 다음과 같습니다:
