Little Cyan Fish רוצה לצבוע $n$ נקודות בצבע ציאן או לבן. הנקודה ה-$i$ נמצאת ב-$(x_i, y_i)$. הנקודות שונות זו מזו בזוגות והן הקודקודים של מצולע קמור ממש, הרשומים נגד כיוון השעון.

תהי $H_c$ הקמור של הנקודות בצבע ציאן, ותהי $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}$.