ในดินแดนอันห่างไกล มีป้อมปราการแห่งหนึ่ง หากเราแสดงทิศทางโดยใช้ระบบพิกัดคาร์ทีเซียน อาณาเขตของป้อมปราการสามารถมองเป็นวงกลมที่มีจุดศูนย์กลางอยู่ที่จุดกำเนิดและมีรัศมี $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)$ แทนพิกัดของมุมบนขวา รับประกันว่ารูปสี่เหลี่ยมผืนผ้าทั้งหมดอยู่ภายในอาณาเขตป้อมปราการอย่างแท้จริงและไม่แตะเส้นขอบของอาณาเขต
- บรรทัดสุดท้ายประกอบด้วยจำนวนเต็มสองจำนวน $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$) แทนพิกัดของ Little S รับประกันว่าจุด $(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
หมายเหตุ
สำหรับชุดข้อมูลทดสอบแรก ภาพประกอบที่สอดคล้องกันเป็นดังนี้:
สำหรับชุดข้อมูลทดสอบที่สอง ภาพประกอบที่สอดคล้องกันเป็นดังนี้:
