Presek konveksnih mnogouglova

Napisati program koji određuje presek dva konveksna mnogougla.

Opis ulaza

Sa standardnog ulaza se učitava broj \(m (3 \leq m \leq 10^5)\) koji predstavlja broj temena prvog mnogougla \(P\), zatim se učitava niz \(x\)-koordinata temena tog mnogougla, a zatim niz \(y\)-koordinata tih temena. Temena su zadata redom, u pozitivnom matematičkom smeru, a koordinate su im realni brojevi zadati sa najviše 5 decimala.

Nakon toga se u istom formatu unose i podaci za drugi mnogougao \(Q\): broj temena \(n (3 \leq n \leq 10^5)\), niz \(x\)-koordinata i niz \(y\)-koordinata.

Opis izlaza

Na standradni izlaz ispisati koordinate konveksnog mnogougla koji je presek mnogouglova \(P\) i \(Q\). Ispisati njegov broj temena, zatim niz \(x\)-koordinata temena i zatim niz \(y\)-koordinata temena. Temena ispisivati redom, u pozitivnom matematičkom smeru (krenuvši od proizvoljnog temena). Koordinate svih temena ispisati zaokružene na 5 decimala.

Primer 1

Ulaz

3
-3 -1 4
-1 5 -1
3
-4 5 4
4 -2 4

Izlaz

5
-1.81818 -1.33333 -0.16667 4.00000 3.50000 
2.54545 4.00000 4.00000 -1.00000 -1.00000 

Objašnjenje

Mnogouglovi i njihov presek su prikazni na slici.

Primer 2

Ulaz

3
-3 0 3
5 0 5
4
-1 1 1 -1
2 2 4 4

Izlaz

4
-1.00000 1.00000 1.00000 -1.00000
2.00000 2.00000 4.00000 4.0000

Objašnjenje

Mnogouglovi i njihov presek su prikazni na slici.

Primer 3

Ulaz

3
-3 0 3
5 0 5
4
2 4 2 4
0 0 2 2

Izlaz

0

Objašnjenje

Mnogouglovi su prikazni na slici. Oni se ne seku

Primer 4

Ulaz

4
0 1 1 0
0 0 1 1
4
1 2 2 1
1 1 2 2

Izlaz

1
1.00000
1.00000

Rešenje