Fişierul intrare/ieşire:geometrie.in, geometrie.outSursăUrmasii lui Moisil 2015, Clasele 11-12
AutorPaul DiacAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 AiA}
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.ingeometrie.out
3 3
1 3
4 5
5 1
3 3
6 8
8 4
0.0
15.0
14.5
geometrie.ingeometrie.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:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?