En una tierra lejana hay una fortaleza. Si representamos la orientación mediante un sistema de coordenadas cartesianas, el territorio de la fortaleza puede verse como un círculo centrado en el origen con radio $R$. El límite del territorio de la fortaleza está rodeado de altos muros, y es imposible ver el exterior desde el interior de la fortaleza.
Dentro de la fortaleza hay algunos edificios. Por conveniencia, los límites de los edificios se representan mediante $n$ rectángulos posiblemente superpuestos cuyos lados son paralelos a los ejes de coordenadas. Un punto dentro de la fortaleza se considera bloqueado si se encuentra estrictamente en el interior de cualquiera de los rectángulos (los puntos en el borde de los rectángulos no se consideran en el interior).
Little S es un guardia de esta fortaleza. Se encuentra en algún punto no bloqueado $(x, y)$ dentro de la fortaleza. Little S puede vigilar otro punto $(x', y')$ dentro de la fortaleza si y solo si todos los puntos del segmento de recta $(x, y) - (x', y')$ (incluidos ambos extremos) no están bloqueados. La tarea consiste en calcular el área del conjunto de puntos que Little S puede vigilar, lo que representa el área de terreno de la fortaleza que Little S puede supervisar.
Entrada
Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^5$), que indica el número de casos de prueba.
Para cada caso de prueba:
- La primera línea contiene dos enteros $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), que representan el radio de la fortaleza y el número de rectángulos.
- Las siguientes $n$ líneas contienen cada una cuatro enteros $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$), que describen un rectángulo, donde $(x_1, y_1)$ representa las coordenadas de la esquina inferior izquierda y $(x_2, y_2)$ representa las coordenadas de la esquina superior derecha. Se garantiza que todos los rectángulos están estrictamente dentro del territorio de la fortaleza y no tocan el borde del territorio.
- La última línea contiene dos enteros $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), que representan las coordenadas de Little S. Se garantiza que el punto $(x, y)$ no está bloqueado.
Se garantiza que la suma total de $n$ en todos los casos de prueba no supera $10^5$.
Salida
Para cada caso de prueba, imprime una sola línea con un número real que represente el área del conjunto de puntos que Little S puede vigilar dentro de la fortaleza.
La respuesta se considerará correcta si el error relativo o absoluto en comparación con la respuesta estándar es menor que $10^{-6}$. En otras palabras, si tu salida es $a$ y la respuesta estándar es $b$, tu salida se considera correcta si y solo si $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.
Ejemplo
Entrada
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
Salida
5.598332050807308 513.142778328943998
Nota
Para el primer caso de prueba, la imagen correspondiente es la siguiente:
Para el segundo caso de prueba, la imagen correspondiente es la siguiente:
