במשחק וידאו דו-ממדי מבוסס פיזיקה, שתי דמויות $P$ ו-$Q$ נעות ברחבי שדה הקרב. כל דמות מיוצגת על ידי מצולע קמור המשמש כתיבת ההתנגשות (collision box) שלה. כאשר שתי תיבות ההתנגשות חופפות, המשחק מחשב את שטח החיתוך שלהן כנזק ההתנגשות.
אולם, בשל זרמי רוח בלתי צפויים בזירה, הדמות $Q$ יכולה להיות מוזזת על ידי וקטור הזזה שרירותי $\mathbf{t} = (t_x, t_y)$, אך אינה יכולה להסתובב או להתהפך. עליכם לחשב את תוחלת נזק ההתנגשות כאשר $Q$ ממוקמת באופן אחיד ואקראי כך שהיא אכן מתנגשת עם $P$, כלומר לחיתוך שלהן יש שטח חיובי.
באופן פורמלי יותר, נגדיר את $f(\mathbf{t})$ כשטח החיתוך בין המצולע המייצג את הדמות $P$ לבין המצולע המייצג את הדמות $Q$ לאחר הזזה לאורך $\mathbf{t}$. תהי $D \subseteq \mathbb{R}^2$ קבוצת כל וקטורי ההזזה $\mathbf{t}$ שעבורם $f(\mathbf{t}) > 0$. ניתן להראות של-$D$ יש שטח חיובי, המסומן ב-$|D|$. עליכם לחשב את $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.
קלט
השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 300$), המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:
- השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$m$ ($3 \le n, m \le 1\,000$), המציינים את מספרי הקודקודים של שני המצולעים הקמורים, בהתאמה.
- לאחר מכן מופיעות $n$ שורות, שכל אחת מהן מכילה שני מספרים שלמים $x$ ו-$y$ ($-10^4 \le x, y \le 10^4$), הנותנים את קואורדינטות הקודקודים $(x, y)$ של המצולע המייצג את הדמות $P$.
- לאחר מכן מופיעות $m$ שורות, שכל אחת מהן מכילה שני מספרים שלמים $x$ ו-$y$ ($-10^4 \le x, y \le 10^4$), הנותנים את קואורדינטות הקודקודים $(x, y)$ של המצולע המייצג את הדמות $Q$.
- מובטח שקודקודי המצולע הקמור ניתנים נגד כיוון השעון, ואין שלושה מהם שנמצאים על ישר אחד.
מובטח שגם סכום ה-$n$-ים וגם סכום ה-$m$-ים על פני כל מקרי הבדיקה אינם עולים על $1\,000$.
פלט
עבור כל מקרה בדיקה, הדפיסו שורה המכילה מספר ממשי המייצג את תוחלת נזק ההתנגשות.
תשובתכם תתקבל אם השגיאה המוחלטת או היחסית שלה אינה עולה על $10^{-6}$. באופן פורמלי, נניח שהפלט שלכם הוא $a$ ותשובת השופטים היא $b$; הפלט שלכם יתקבל אם ורק אם $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.
דוגמאות
קלט 1
2 3 3 0 0 1 0 0 1 0 0 1 0 0 1 3 3 0 0 1 0 0 1 0 1 1 0 1 1
פלט 1
0.083333333333 0.125000000000