Zadanie

Joj, veď nebuď mäkký

Počet bodov: 85

— “Geometria na celoštátku?”

— “Joj, veď nebuď mäkký”

— “Ale čo tam dáme? Obsah? Ťažisko? Konvexný obal?”

— “To je príliš známe …”

— “Niečo 3D?”

— “A pripravíš to?”

— “Nooo …”

— “Čo tak prekryv dvoch objektov?”

— “Napríklad mnohouholníkov?”

— “Ale tam môže byť kvadraticky veľa priesečníkov”

— “Pravda … jedine, že by boli konvexné”

— “Hmmm”

— “Hmmm?”

— “Mhmmm!”

Úloha

Na vstupe sú dva konvexné mnohouholníky. Zistite koľko vrcholov má ich prienik.

Mnohouholník je konvexný, ak sú všetky jeho vnútorné uholy strikne menšie ako \(180^{\circ}\).

Prienik dvoch útvarov je množina bodov, ktoré sa nachádzajú súčasne v prvom aj v druhom útvare. Dá sa ľahko odôvodniť, že prienik dvoch mnohouholníkov je tiež mnohouholník.

Vstup

Prvý riadok vstupu obsahuje jedno celé číslo \(N\) - počet vrcholov prvého mnohouholníka. Každý z nasledujúcich \(N\) riadkov obsahuje \(2\) medzerou oddelené celé čísla \(x_i y_i\) - súradnice vrcholov prvého mnohouholníka.

Nasleduje rovanký popis druhého mnohouholníka, teda riadok s počtom vrcholov \(M\) a následne \(M\) riadkov s medzerou oddelenými súradnicami \(x_i y_i\).

Platí že:

• \(3 \leq N, M\)
• \(-10^9 < x_i, y_i < 10^9\) pre súradnice oboch mnohouholníkov
• Vrcholy mnohouholníkov sú zadané vždy v poradí v akom sú na obvode
• Vrcholy mnohouholníkov sú zadané vždy proti smeru hodinových ručičiek (ak X rastie doprava a Y hore)
• Mnohouholníky nezdielajú žiaden vrchol
• Vrchol žiadneho mnohouholníka neleží na hrane druhého mnohouholníka
• Mnohouholníky majú vždy nejaký prienik

Limity pre sady: - Pre \(1.\) sadu vstupov za \(25b\) platí: \(N = M = 3\) - Pre \(2.\) sadu vstupov za \(25b\) platí: \(N, M \leq 800\) - Pre \(3.\) sadu vstupov za \(35b\) platí: \(N, M \leq 60 000\)

Výstup

Na jediný riadok výstupu vypíšte jedno celé číslo - počet vrcholov, ktoré má prienik mnohouholníkov na vstupe.

Príklad

Input:

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

Output:

8

Na vstupe sú dva štvorce, ktoré sa pretínajú do hviezdy. Ich prienik je osemuholník

Input:

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

Output:

3

Trojuholník sa nachádza kompletne vo vnútri štvorca - prienik je totožný s trojuholníkom na vstupe.

Input:

3
1 -1
0 3
-1 -1
3
3 0
0 1
-3 0

Output:

5

Na vstupe je široký a vysoký trojuholník - prienik je tiež päťuholník.