Fişierul intrare/ieşire:	combl.in, combl.out	Sursă	Infoarena Cup 2014
Autor	Cosmin Gheorghe	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Combl

Fie S o multime de perechi (a,b) de numere naturale. S = {(a₁,b₁), (a₂,b₂), (a₃,b₃), ...}

Spunem ca o pereche (x,y) este S-compatibila daca se poate scrie ca combinatie liniara a perechilor din S cu coeficienti din [0, 1].

Mai exact perechea (x,y) este S-compatibila daca exista coeficientii reali c₁, c₂, ..., c_N apartinand intervalului [0, 1] astfel incat

• x = c₁ * a₁ + c₂ * a₂ + c₃ * a₃ + ... + c_N * a_N
• y = c₁ * b₁ + c₂ * b₂ + c₃ * b₃ + ... + c_N * b_N

unde (a₁,b₁), (a₂,b₂), (a₃,b₃), ..., (a_N,b_N) sunt perechile din S.

Pornind de la o multime S initial vida trebuie sa puteti suporta urmatoarele operatii:

• Insert (a,b) - se insereaza perechea (a,b) in S
• Erase (a,b) - se sterge perechea (a,b) din S
• Query (x,y) - se verifica daca perechea (x,y) este S-compatibila

Date de intrare

Fişierul de intrare combl.in va contine pe prima linie un singur numar natural Q reprezentand numarul de operatii ce trebuiesc executate.
Urmatoarele Q linii vor descrie fiecare cate o operatie, astfel

• Daca primul numar de pe linie este egal cu 1 operatia descrisa este o operatie de tip Insert. Dupa numarul 1 vor urma 2 numere naturale a si b reprezentand perechea ce va fi adaugata multimii S.
• Daca primul numar de pe linie este egal cu 2 operatia descrisa este o operatie de tip Erase. Dupa numarul 2 vor urma 2 numere naturale a si b reprezentand perechea ce va fi stearsa din multimea S.
• Daca primul numar de pe linie este egal cu 3 operatia descrisa este o operatie de tip Query. Dupa numarul 3 vor urma 2 numere naturale x si y reprezentand perechea pentru care se interogheaza daca este S-compatibila sau nu.

Date de ieşire

În fişierul de ieşire combl.out trebuie sa se gaseasca tot atatea linii cate operatii de tip Query au fost in fisierul de intrare combl.in.
Astfel, pe linia a i-a din fisierul de iesire trebuie sa se gaseasca cuvantul "DA" (fara ghilimele) daca perechea (x,y) de la a i-a operatie de tip Query era S-compatibila cu multimea S de la momentul respectiv sau "NU" (fara ghilimele) in caz contrar.

Restricţii

• 1 ≤ Q ≤ 150.000
• 0 ≤ numarul de operatii de tip Insert ≤ 50.000
• 1 ≤ a_i, b_i ≤ 10.000
• 0 ≤ x, y ≤ 1.500.000.000
• Perechile de la operatiile de tip Insert sunt diferite doua cate doua
• Orice operatie de tip Erase este valida, mai exact nu va exista operatie de sterge a unei perechi (a,b) daca perechea (a,b) nu face parte din S
• Orice operatie de tip Query este valida, mai exact oricand va aparea o astfel de operatie multimea S va fi nevida
• Pentru teste in valoare de 20 de puncte nu vor fi decat 2 operatii de tip Insert in fisierul de intrare
• Pentru alte teste in valoare de 40 de puncte Q ≤ 3.000

Exemplu

Explicaţie

• La prima operatie de tip Query multimea S este formata din perechile (1,2) si (2,1).
  Putem obtine perechea (2,2) ca
  • x = 2/3 * 1 + 2/3 * 2 = 2
  • y = 2/3 * 2 + 2/3 * 1 = 2
• La a doua operatie de tip Query multimea S este formata doar din perechea (2,1). Nu putem obtine (2,2) in niciun fel.
• La a treia operatie de tip Query multimea S este formata din perechile (2,1), (1,3) si (4,2). Pentru a obtine x = 0 trebuie ca toti coeficientii c sa fie egali cu 0, deci si y ar trebui sa fie egal cu 0, insa noi avem nevoie de y = 3.
• La a patra operatie de tip Query multimea S este formata din perechile (2,1), (1,3) si (4,2).
  Putem obtine perechea (5,4) ca
  • x = 0.2 * 2 + 0.6 * 1 + 1 * 4 = 0.4 + 0.6 + 4 = 5
  • y = 0.2 * 1 + 0.6 * 3 + 1 * 2 = 0.2 + 1.8 + 2 = 4

Cum se trimit solutii?