Geometrie

geometrie

Pe prima linie a fişierului $geometrie.in$ se află numerele naturale nenule {**N**} şi {**M**}.
Următoarele {**N**} linii conţin câte două numere {**Ai.x Ai.y**} separate prin spaţiu.
Următoarele {**M**} linii conţin câte două numere {**Q.x Q.y**} separate prin spaţiu.

În fişierul de intrare atât punctele {**Ai**} cât şi punctele {**Q**} sunt în ordinea crescătoare a valorilor {**x**}.

În fişierul de intrare atât punctele {**Ai**} cât şi punctele {**Q**} sunt în ordinea crescătoare a valorilor x.

h2. Date de ieşire

h2. Restricţii

•	{**N, M**} <= 10^5^
•	0 <= {**Ai.x**}, {**Ai.y**}, {**Q.x**} şi {**Q.y**} <= 10^9^
•	Punctele din mulţimea {**A**} au valori {**Ai.x**} distincte.

•	N, M <= 10 ^5^
•	0 <= Ai.x, Ai.y, Q.x şi Q.y <= 10^9^
•	Punctele din mulţimea A au valori Ai.x distincte.

•	Înfăşurătoarea convexă a unei mulţimi cu cel mult două puncte are aria egală cu zero.

•	Pentru teste în valoare de {**20**} puncte {**N**} <= 3
•	Pentru teste în valoare de {**40**} puncte {**N×M**} <= 10^3^
•	Pentru teste în valoare de {**60**} puncte {**N×M**} <= 10^6^

•	Pentru teste în valoare de 20 puncte N <= 3
•	Pentru teste în valoare de 40 puncte N×M <= 10^3^
•	Pentru teste în valoare de 60 puncte N×M <= 10^6^

h2. Exemplu

table(example). |_. geometrie.in |_. geometrie.out |

table(example). |_. geometrie.in |_. geometrie.out |_. geometrie.in |_. geometrie.out |

|3 3
1 3
4 5

| 0.0
15.0
14.5

|
 
table(example). |_. geometrie.in |_. geometrie.out |

|9 2
1 3
3 5

|

h3. Explicaţie pentru al doilea exemplu:

h3. Explicaţie pentru testul din partea dreaptă:

{! problema/geometrie?exemplu1.jpg 42% !}

{! problema/geometrie?exemplu1.jpg 44% !}

{! problema/geometrie?exemplu2.jpg 42% !}

{! problema/geometrie?exemplu2.jpg 44% !}