| Fişierul intrare/ieşire: | points2.in, points2.out | Sursă | Shumen 2019 Juniori |
| Autor | Adăugată de |  Matteo Verzotti •Matteoalexandru | |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Points2
Se dau N puncte in planul XOY cu coordonatele numere intregi. Un punct se numeste extern daca ambele conditii sunt indeplinite simultan:
1. Poate fi mutat oricat de mult la stanga sau la dreapta fara sa atinga un alt punct
2. Poate fi mutat oricat de mult in sus sau in jos fara sa atinga un alt punct.
Un punct se numeste intern daca acesta nu poate fi mutat oricat de mult nici la stanga/dreapta nici in sus/jos fara sa atinga un alt punct.
Scrieti un program care gaseste numarul de puncte externe si numarul de puncte interne din configuratia initiala si apoi executa operatii de doua tipuri: "adaugare punct" si "stergere punct". Dupa fiecare operatie se cere, din nou, numarul nou de puncte externe si numarul nou de puncte interne.
Date de intrare
Fişierul de intrare points2.in contine pe prima linie numarul N de puncte initial. Pe fiecare din urmatoarele N linii se afla doua numere intregi pozitive, separate printr-un spatiu, ce reprezinta coordonatele fiecarui punct. Pe linia N + 2 se afla un numar natural Q, ce reprezinta numarul de operatii care trebuie efectuate. Pe urmatoarele Q linii se afla 3 numere intregi pozitive: primul numar poate fi 1 - daca adaugam un punct sau 2 - daca stergem un punct. Urmatoarele doua numere constituie coordonatele punctului ce trebuie adaugat/sters.
Date de ieşire
În fişierul de ieşire points2.out se vor afla Q + 1 linii. Pe prima linie se va afla numarul initial de puncte externe si interne. Pe linia i + 1 se va afla numarul de puncte externe si interne dupa operatia i.
Restricţii
- 0 < N ≤ 100.000
- 0 < Q ≤ 100.000
- 0 < coordonatele fiecarui punct ≤ 100.000
- Se garanteaza ca la fiecare operatie de tipul 2, punctul ce trebuie sters se afla in plan.
- Se garanteaza ca la fiecare moment nu vor exista 2 sau mai multe puncte cu aceleasi coordonate simultan in plan.
- Pentru 40% din teste, Q ≤ 2000 si nu exista mai mult de 2000 de puncte simultan in plan.
Exemplu
| points2.in | points2.out |
|---|---|
| 10 1 4 2 1 1 2 3 4 4 2 2 2 1 1 3 1 3 2 4 3 3 1 4 4 2 1 1 1 2 3 | 6 1 5 1 6 1 7 2 |
Explicatie
Setul initial de puncte este dat in figura de mai sus. Punctul intern este notat cu □, punctele externe sunt notate cu ▪, iar restul punctelor sunt notate cu o
