Ở một vùng đất xa xôi, có một pháo đài. Nếu biểu diễn phương hướng bằng hệ tọa độ Descartes, lãnh thổ của pháo đài có thể được xem như một hình tròn tâm tại gốc tọa độ với bán kính $R$. Ranh giới lãnh thổ pháo đài được bao quanh bởi những bức tường cao, và không thể nhìn thấy bên ngoài từ bên trong pháo đài.
Bên trong pháo đài có một số tòa nhà. Để thuận tiện, ranh giới của các tòa nhà được biểu diễn bởi $n$ hình chữ nhật có thể giao nhau và có các cạnh song song với các trục tọa độ. Một điểm bên trong pháo đài được coi là bị che khuất nếu nó nằm hoàn toàn bên trong bất kỳ hình chữ nhật nào (các điểm nằm trên biên của hình chữ nhật không được coi là nằm bên trong).
Little S là lính canh của pháo đài này. Anh đứng tại một điểm không bị che khuất $(x, y)$ bên trong pháo đài. Little S có thể canh gác một điểm khác $(x', y')$ bên trong pháo đài khi và chỉ khi mọi điểm trên đoạn thẳng $(x, y) - (x', y')$ (bao gồm cả hai đầu mút) đều không bị che khuất. Nhiệm vụ của bạn là tính diện tích tập hợp các điểm mà Little S có thể canh gác, biểu thị diện tích vùng đất pháo đài mà Little S có thể giám sát.
Dữ liệu vào
Bài toán này gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), cho biết số lượng bộ dữ liệu.
Với mỗi bộ dữ liệu:
- Dòng đầu tiên chứa hai số nguyên $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), lần lượt biểu thị bán kính của pháo đài và số lượng hình chữ nhật.
- $n$ dòng tiếp theo, mỗi dòng chứa bốn số nguyê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$), mô tả một hình chữ nhật, trong đó $(x_1, y_1)$ là tọa độ góc dưới bên trái và $(x_2, y_2)$ là tọa độ góc trên bên phải. Dữ liệu đảm bảo tất cả các hình chữ nhật đều nằm hoàn toàn bên trong lãnh thổ pháo đài và không chạm vào biên của lãnh thổ.
- Dòng cuối cùng chứa hai số nguyên $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), biểu thị tọa độ của Little S. Dữ liệu đảm bảo điểm $(x, y)$ không bị che khuất.
Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^5$.
Kết quả
Với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số thực biểu thị diện tích tập hợp các điểm mà Little S có thể canh gác bên trong pháo đài.
Câu trả lời sẽ được coi là đúng nếu sai số tương đối hoặc tuyệt đối so với đáp án chuẩn nhỏ hơn $10^{-6}$. Nói cách khác, nếu kết quả của bạn là $a$ và đáp án chuẩn là $b$, kết quả của bạn được coi là đúng khi và chỉ khi $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.
Ví dụ
Dữ liệu vào
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
Kết quả
5.598332050807308 513.142778328943998
Ghi chú
Với bộ dữ liệu đầu tiên, hình minh họa tương ứng như sau:
Với bộ dữ liệu thứ hai, hình minh họa tương ứng như sau:
