points2

Points2

== include(page="template/taskheader" task_id="points2") ==

Poveste şi cerinţă...

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$.

h2. Date de intrare

Fişierul de intrare $points2.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $points2.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0 < N &le; 100.000$
* $0 < Q &le; 100.000$
* $0 < coordonatele fiecarui punct &le; 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 &le; 2000$ si nu exista mai mult de $2000$ de puncte simultan in plan.

h2. Exemplu
table(example). |_. points2.in |_. points2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 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
|
 
h3. Explicatie

h3. Explicaţie

!problema/points2?Exemplu.PNG!

...

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

== include(page="template/taskfooter" task_id="points2") ==