Fişierul intrare/ieşire:triunghiuri.in, triunghiuri.outSursăFMI No Stress 10
AutorSeritan LucaAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Triunghiuri

Un nou grup infracţional, Z, a aparut la tine in oras si incearca sa distruga Craciunul. Se ştie că harta oraşului este un plan cu diverse locaţii importante, reprezentate drept puncte in acest plan.
Z actioneaza într-un mod foarte specific: intotdeauna atacă câte 3 puncte de interes, dar doar dacă aria triunghiului format de acestea este un număr întreg (inclusiv 0).

Deoarece eşti cel mai iscusit programator, autorităţile ţi-au cerut ajutorul pentru a salva sărbătorile.
Cunoscând cele N locaţii iniţiale şi Q modificări pe care le suferă harta, trebuie să realizezi un program care calculează în cate moduri ar putea infractorii să ţintească 3 puncte, atât pentru configuraţia iniţială, cât şi după fiecare modificare.

Date de intrare

Fişierul de intrare triunghiuri.in conţine pe prima linie 2 numere: N şi Q.
Pe următoarele N linii se găsesc coordonatele celor N puncte iniţiale.
Pe următoarele Q linii este descrisă câte o operaţie. Acestea pot fi de două tipuri:
- 1 X Y - se inserează un nou punct la coordonatele (X, Y). Se garanteaza că acest punct nu există deja.
- 2 X Y - se şterge un punct de la coordonatele (X, Y). Se garantează că acest punct există deja.

Date de ieşire

În fişierul de ieşire triunghiuri.out se vor afişa Q+1 linii, numărul de modalităţi de a alege 3 puncte respectând cerinţa, atât pentru configuraţia iniţială precum şi după fiecare actualizare.

Restricţii

  • 1 ≤ N ≤ 10000
  • 0 ≤ Q ≤ 10000
  • -109 ≤ x, y ≤ 109
  • Toate coordonatele sunt numere intregi
  • Pentru 50% din teste se garanteaza ca n ≤ 100 si q = 0.
  • Un triunghi degenerat (de arie 0) este considerat intreg.
  • O modificare anterioara se pastreaza si pentru modificarile ce o urmeaza.

Exemplu

triunghiuri.intriunghiuri.out
5 0
5 8
9 2
9 9
9 -6
10 -5
7
5 5
5 -4
-2 3
-5 9
5 -8
4 1
2 4 1
1 8 9
2 5 -8
1 4 2
1 4 3
6
2
6
2
3
10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?