== include(page="template/taskheader" task_id="geometrie") ==
Mulţimea A conţine N puncte Ai în plan de coordonate întregi cunoscute (Ai.x, Ai.y).
Pentru o întrebare definită printr-un punct Q = (Q.x, Q.y) se cere aria înfăşurătorii convexe a punctelor:
{Q} ∪ {Ai | Ai.x < Q.x şi Ai ∈ A}
Determinaţi răspunsul pentru o serie de M întrebări de acest tip relative la mulţimea iniţială A.
Mulţimea {**A**} conţine {**N**} puncte {**Ai**} în plan de coordonate întregi cunoscute {**(Ai.x**}, {**Ai.y**}).
Pentru o întrebare definită printr-un punct {**Q**} = ({**Q.x**}, {**Q.y**}) se cere aria înfăşurătorii convexe a punctelor:
{{**Q**}} ∪ {{**Ai**} | {**Ai.x**} < {**Q.x**} şi {**Ai**} ∈ {**A**}}
Determinaţi răspunsul pentru o serie de {**M**} întrebări de acest tip relative la mulţimea iniţială {**A**}.
Înfăşurătoarea convexă a unei mulţimi de puncte este poligonul convex de arie minimă care conţine toate punctele în interior sau pe laturile acestuia.
h2. Date de intrare
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.
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**}.
h2. Date de ieşire
În fişierul $geometrie.out$ afişati M linii cu răspunsurile la întrebări în ordine.
În fişierul $geometrie.out$ afişati {**M**} linii cu răspunsurile la întrebări în ordine.
Afişaţi răspunsul cu o zecimală precizie.
h2. Restricţii
• N, M <= 10 <sup>5</sup>
• 0 <= Ai.x, Ai.y, Q.x şi Q.y <= 10<sup>9</sup>
• 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<sup>3</sup>
• Pentru teste în valoare de 60 puncte N×M <= 10<sup>6</sup>
• 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 |_. geometrie.in |_. geometrie.out |
table(example). |_. geometrie.in |_. geometrie.out |
|3 3
1 3
4 5
