Little Cyan Fish ต้องการระบายสีจุด $n$ จุดด้วยสีฟ้าอมเขียว (cyan) หรือสีขาว จุดที่ $i$ อยู่ที่พิกัด $(x_i, y_i)$ จุดทั้งหมดแตกต่างกันเป็นคู่ๆ และเป็นจุดยอดของรูปหลายเหลี่ยมนูนอย่างแท้จริง (strictly convex polygon) โดยเรียงตามลำดับทวนเข็มนาฬิกา

ให้ $H_c$ เป็นเปลือกนูน (convex hull) ของจุดสีฟ้าอมเขียว และให้ $H_w$ เป็นเปลือกนูนของจุดสีขาว เปลือกนูนคือเซตนูนที่เล็กที่สุดที่บรรจุจุดที่กำหนด เปลือกนูนของเซตว่างคือเซตว่าง และเปลือกนูนที่ประกอบด้วยจุดเพียงจุดเดียวหรือส่วนของเส้นตรงเพียงเส้นเดียวจะมีพื้นที่เป็นศูนย์

จงหาพื้นที่ที่มากที่สุดที่เป็นไปได้ของ $H_c \cap H_w$ ซึ่งเป็นบริเวณที่ทับซ้อนกันของเปลือกนูนทั้งสอง

ภาพประกอบของข้อมูลทดสอบสองชุดแรกในตัวอย่าง (ชุดแรกอยู่ทางซ้าย ชุดที่สองอยู่ทางขวา)

ข้อมูลนำเข้า

มีข้อมูลทดสอบหลายชุด บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับข้อมูลทดสอบแต่ละชุด บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($3 \le n \le 10^5$) แทนจำนวนจุด ในอีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวนคือ $x_i$ และ $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) แทนพิกัดของจุดที่ $i$

รับประกันว่าผลรวมของ $n$ จากข้อมูลทดสอบทั้งหมดจะไม่เกิน $10^5$

ข้อมูลส่งออก

สำหรับข้อมูลทดสอบแต่ละชุด ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนจริงหนึ่งจำนวน แทนพื้นที่ที่มากที่สุดที่เป็นไปได้ของส่วนตัดกันของเปลือกนูนทั้งสอง

คำตอบของคุณจะได้รับการยอมรับหากค่าคลาดเคลื่อนสัมบูรณ์หรือค่าคลาดเคลื่อนสัมพัทธ์ไม่เกิน $10^{-8}$ กล่าวอย่างเป็นทางการคือ ให้ผลลัพธ์ของคุณเป็น $a$ และคำตอบของกรรมการเป็น $b$ ผลลัพธ์ของคุณจะได้รับการยอมรับก็ต่อเมื่อ $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$

ตัวอย่าง

ข้อมูลนำเข้า 1

3
7
0 0
3 0
4 1
3 3
1 4
-1 3
-1 1
5
0 0
2 0
3 1
1 3
-1 1
7
-1000000000 -1000000000
-500000001 -500000002
499999998 499999995
999999998 999999994
500000000 499999997
-499999999 -500000000
-999999999 -999999999

ข้อมูลส่งออก 1

5.944444444444444444
0
2.458333333333333404

หมายเหตุ

ในข้อมูลทดสอบชุดแรกของตัวอย่าง Little Cyan Fish ระบายสีจุดที่ $1$, $2$, $4$ และ $6$ เป็นสีฟ้าอมเขียว และระบายสีจุดอื่นๆ เป็นสีขาว รูปสี่เหลี่ยมสีฟ้าอมเขียวและรูปสามเหลี่ยมสีขาวทับซ้อนกันเป็นพื้นที่ $\frac{107}{18}$ ซึ่งเป็นพื้นที่ที่มากที่สุดที่เป็นไปได้

ในข้อมูลทดสอบชุดที่สองของตัวอย่าง มีอย่างน้อยหนึ่งสีที่มีจุดอย่างมากสองจุด ดังนั้นส่วนตัดกันจึงมีพื้นที่เป็นศูนย์ ภาพประกอบแสดงจุดที่ $1$, $3$ และ $5$ ที่ระบายสีฟ้าอมเขียว ส่วนเปลือกนูนสีขาวคือส่วนของเส้นตรงที่เชื่อมระหว่างจุดที่ $2$ และ $4$

ในข้อมูลทดสอบชุดที่สามของตัวอย่าง การระบายสีจุดที่ $1$, $4$ และ $6$ เป็นสีฟ้าอมเขียว และจุดอื่นๆ เป็นสีขาว จะให้พื้นที่ส่วนตัดกันมากที่สุดเท่ากับ $\frac{59}{24}$