2D-fysiikkapohjaisessa videopelissä kaksi hahmoa $P$ ja $Q$ liikkuvat taistelukentällä. Kumpaakin hahmoa edustaa kupera monikulmio, joka toimii sen törmäyslaatikkona (collision box). Kun kaksi törmäyslaatikkoa menevät päällekkäin, peli laskee niiden leikkauksen pinta-alan törmäysvahingoksi.

Areenan arvaamattomien tuulivirtausten vuoksi hahmo $Q$ voi kuitenkin siirtyä mielivaltaisen siirtovektorin $\mathbf{t} = (t_x, t_y)$ verran, mutta se ei voi pyöriä eikä peilautua. Sinun tulee laskea törmäysvahingon odotusarvo, kun $Q$ sijoitetaan tasaisesti ja satunnaisesti siten, että se todella törmää hahmoon $P$, eli niiden leikkauksella on positiivinen pinta-ala.

Muodollisemmin määritellään $f(\mathbf{t})$ hahmoa $P$ edustavan monikulmion ja vektorin $\mathbf{t}$ suuntaisesti siirretyn hahmoa $Q$ edustavan monikulmion leikkauksen pinta-alaksi. Olkoon $D \subseteq \mathbb{R}^2$ kaikkien sellaisten siirtovektorien $\mathbf{t}$ joukko, joilla $f(\mathbf{t}) > 0$. Voidaan osoittaa, että joukolla $D$ on positiivinen pinta-ala, jota merkitään $|D|$:llä. Sinun tulee laskea $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $T$ ($1 \le T \le 300$), joka ilmaisee testitapausten lukumäärän. Jokaiselle testitapaukselle:

• Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$ ($3 \le n, m \le 1\,000$), jotka ilmaisevat kahden kuperan monikulmion kärkien lukumäärät.
• Seuraavilla $n$ rivillä on kullakin kaksi kokonaislukua $x$ ja $y$ ($-10^4 \le x, y \le 10^4$), jotka antavat hahmoa $P$ edustavan monikulmion kärkien koordinaatit $(x, y)$.
• Seuraavilla $m$ rivillä on kullakin kaksi kokonaislukua $x$ ja $y$ ($-10^4 \le x, y \le 10^4$), jotka antavat hahmoa $Q$ edustavan monikulmion kärkien koordinaatit $(x, y)$.
• On taattu, että kuperan monikulmion kärjet annetaan vastapäivään kiertävässä järjestyksessä eivätkä mitkään kolme niistä ole samalla suoralla.

On taattu, että sekä lukujen $n$ summa että lukujen $m$ summa yli kaikkien testitapausten ovat enintään $1\,000$.

Tuloste

Tulosta jokaiselle testitapaukselle rivi, joka sisältää odotettua törmäysvahinkoa vastaavan reaaliluvun.

Vastauksesi hyväksytään, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$. Muodollisesti, jos tulosteesi on $a$ ja tuomariston vastaus on $b$, tulosteesi hyväksytään jos ja vain jos $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Esimerkit

Syöte 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

Tuloste 1

0.083333333333
0.125000000000