problema/points

Points2

Scrie aici despre problema/points2

== include(page="template/taskheader" task_id="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$.
 
h2. 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.
 
h2. 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$.
 
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 |
| 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
 
!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") ==
 

public

task: points2