== include(page="template/taskheader" task_id="geometrie") ==
Poveste şi cerinţă...
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
Fişierul de intrare $geometrie.in$ ...
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 de ieşire $geometrie.out$ ...
Î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^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^
h2. Exemplu
table(example). |_. geometrie.in |_. geometrie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|3 3
1 3
4 5
5 1
3 3
6 8
8 4
| 0.0
15.0
14.5
|
table(example). |_. geometrie.in |_. geometrie.out |
|9 2
1 3
3 5
4 1
6 4
8 6
9 1
10 3
11 5
13 2
4 3
10 4
|3.0
32.0
|
h3. Explicaţie pentru al doilea exemplu:
{! problema/geometrie?exemplu1.jpg 42% !}
h3. Explicaţie
{! problema/geometrie?exemplu1.jpg 40% !}
{! problema/geometrie?exemplu2.jpg 40% !}
{! problema/geometrie?exemplu2.jpg 42% !}
