Í tvívíðum eðlisfræðitölvuleik hreyfast tvær persónur $P$ og $Q$ um vígvöllinn. Hver persóna er táknuð með kúptum marghyrningi sem þjónar sem árekstrarrammi (collision box) hennar. Þegar árekstrarrammarnir tveir skarast reiknar leikurinn flatarmál sniðmengis þeirra sem árekstrarskaðann.

Hins vegar, vegna ófyrirsjáanlegra vindstrauma á leikvanginum, getur persóna $Q$ hliðrast um hvaða hliðrunarvigur sem er $\mathbf{t} = (t_x, t_y)$, en hún getur hvorki snúist né speglast. Þú þarft að reikna væntigildi árekstrarskaðans þegar $Q$ er staðsett jafndreift og af handahófi þannig að hún rekist í raun á $P$, þ.e. sniðmengi þeirra hafi jákvætt flatarmál.

Formlegra sagt, skilgreinum $f(\mathbf{t})$ sem flatarmál sniðmengisins milli marghyrningsins sem táknar persónu $P$ og marghyrningsins sem táknar persónu $Q$ eftir að honum hefur verið hliðrað um $\mathbf{t}$. Látum $D \subseteq \mathbb{R}^2$ vera mengi allra hliðrunarvigra $\mathbf{t}$ þannig að $f(\mathbf{t}) > 0$. Sýna má að $D$ hefur jákvætt flatarmál, táknað með $|D|$. Þú þarft að reikna $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 300$), sem táknar fjölda prófunartilvika. Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($3 \le n, m \le 1\,000$), sem tákna fjölda hornpunkta kúptu marghyrninganna tveggja, í sömu röð.
• Síðan fylgja $n$ línur, þar sem hver lína inniheldur tvær heiltölur $x$ og $y$ ($-10^4 \le x, y \le 10^4$), sem gefa hnit hornpunkta $(x, y)$ marghyrningsins sem táknar persónu $P$.
• Síðan fylgja $m$ línur, þar sem hver lína inniheldur tvær heiltölur $x$ og $y$ ($-10^4 \le x, y \le 10^4$), sem gefa hnit hornpunkta $(x, y)$ marghyrningsins sem táknar persónu $Q$.
• Tryggt er að hornpunktar kúpts marghyrnings séu gefnir í rangsælis röð, og engir þrír þeirra liggi á sömu línu.

Tryggt er að hvorki summa $n$ né summa $m$ yfir öll prófunartilvik fari yfir $1\,000$.

Úttak

Fyrir hvert prófunartilvik skal prenta línu sem inniheldur rauntölu sem táknar væntigildi árekstrarskaðans.

Svarið þitt er tekið gilt ef algildis- eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$. Formlega sagt, gerum ráð fyrir að úttakið þitt sé $a$ og svar dómnefndar sé $b$; úttakið þitt er samþykkt ef og aðeins ef $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Dæmi

Inntak 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

Úttak 1

0.083333333333
0.125000000000