| Fişierul intrare/ieşire: | geometrie.in, geometrie.out | Sursă | Urmasii lui Moisil 2015, Clasele 11-12 |
| Autor | Paul Diac | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
Î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.
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.
Date de ieşire
Î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.
Restricţii
• N, M <= 105
• 0 <= Ai.x, Ai.y, Q.x şi Q.y <= 109
• 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 <= 103
• Pentru teste în valoare de 60 puncte N×M <= 106
Exemplu
| geometrie.in | geometrie.out |
|---|---|
| 3 3 1 3 4 5 5 1 3 3 6 8 8 4 | 0.0 15.0 14.5 |
| 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 |
Explicaţie pentru al doilea exemplu:
