Dans une contrée lointaine se trouve une forteresse. Si nous représentons l'orientation à l'aide d'un système de coordonnées cartésiennes, le territoire de la forteresse peut être vu comme un cercle centré à l'origine et de rayon $R$. La frontière du territoire de la forteresse est entourée de hauts murs, et il est impossible de voir l'extérieur depuis l'intérieur de la forteresse.
À l'intérieur de la forteresse se trouvent quelques bâtiments. Par commodité, les limites des bâtiments sont représentées par $n$ rectangles pouvant se chevaucher et dont les côtés sont parallèles aux axes de coordonnées. Un point situé à l'intérieur de la forteresse est considéré comme bloqué s'il se trouve strictement à l'intérieur de l'un des rectangles (les points sur le bord des rectangles ne sont pas considérés comme étant à l'intérieur).
Little S est un garde de cette forteresse. Il se tient en un point non bloqué $(x, y)$ à l'intérieur de la forteresse. Little S peut garder un autre point $(x', y')$ à l'intérieur de la forteresse si et seulement si chaque point du segment $(x, y) - (x', y')$ (y compris les deux extrémités) n'est pas bloqué. La tâche consiste à calculer l'aire de l'ensemble des points que Little S peut garder, ce qui représente la superficie du terrain de la forteresse que Little S peut surveiller.
Entrée
Ce problème contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.
Pour chaque cas de test :
- La première ligne contient deux entiers $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), représentant le rayon de la forteresse et le nombre de rectangles.
- Les $n$ lignes suivantes contiennent chacune quatre entiers $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$), décrivant un rectangle, où $(x_1, y_1)$ représente les coordonnées du coin inférieur gauche et $(x_2, y_2)$ représente les coordonnées du coin supérieur droit. Il est garanti que tous les rectangles sont strictement à l'intérieur du territoire de la forteresse et ne touchent pas la frontière du territoire.
- La dernière ligne contient deux entiers $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), représentant les coordonnées de Little S. Il est garanti que le point $(x, y)$ n'est pas bloqué.
Il est garanti que la somme totale de $n$ sur tous les cas de test ne dépasse pas $10^5$.
Sortie
Pour chaque cas de test, affichez une seule ligne contenant un nombre réel représentant l'aire de l'ensemble des points que Little S peut garder au sein de la forteresse.
La réponse sera considérée comme correcte si l'erreur relative ou absolue par rapport à la réponse officielle est inférieure à $10^{-6}$. Autrement dit, si votre sortie est $a$ et la réponse officielle est $b$, votre sortie est considérée comme correcte si et seulement si $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.
Exemple
Entrée
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
Sortie
5.598332050807308 513.142778328943998
Note
Pour le premier cas de test, l'image correspondante est la suivante :
Pour le second cas de test, l'image correspondante est la suivante :
