== include(page="template/taskheader" task_id="terenuri") ==
Poveste şi cerinţă...
Cei $N$ ţărani din satul Gheorgheni sunt numerotaţi de la $1$ la $N$ si au casele dispuse haotic. Casele sunt reprezentate ca $N$ puncte în plan care au ca şi coordonate numere reale. Ca să îşi organizeze mai bine satul, au decis să-şi împartă pământul astfel: fiecare ţăran va primi un teren astfel încât orice punct de pe suprafaţa acestuia va fi mai aproape de casa lui decât de oricare altă casă. Punctele aflate la egală distanţă de $2$ sau mai multe case vor alcătui gardul, care nu va fi proprietatea nimănui pentru a nu apărea conflicte. Lăcomia lor totuşi iese în evidenţă prin faptul că au uitat de drumuri ( :)) ).
Astfel vor apărea două categorii de ţărani: dominaţi (au vecini de jur-împrejurul curţii) şi liberi (au vecini doar în unele părţi ale curţii).
De-a lungul timpului satul Gheorgheni a devenit atractiv, astfel mai sosesc pe rând $M$ ţărani, fiecare stabilindu-şi casa într-un punct de coordonate reale. După sosirea fiecăruia, se reîmpart terenurile şi se doreşte aflarea numărului de ţărani liberi.
h2. Cerinţă
Să se găsească şi să se afişeze numărul ţăranilor liberi la început şi după fiecare sosire a unui ţăran nou.
h2. Date de intrare
Fişierul de intrare $terenuri.in$ ...
Fişierul de intrare $terenuri.in$ conţine pe prima linie $N$ şi $M$, reprezentând numărul initial de ţărani ai satului Gheorgheni si numărul de ţărani care se vor muta îin sat. Următoarele $N$ linii vor conţine câte două numere reale, reprezentând coordonatele caselor ţăranilor iniţiali (băştinaşii) (linia $i$ conţine coordonatele casei ţăranului $i$).
Apoi urmează $M$ linii, fiecare conţinând două numere reale $x$ şi $y$, reprezentând coordonatele casei unui ţăran nou venit.
h2. Date de ieşire
În fişierul de ieşire $terenuri.out$ ...
Fişierul de ieşire $terenuri.out$ va conţine pe prima linie numărul iniţial al ţăranilor liberi. Următoarele $M$ linii conţin numărul de ţărani liberi după fiecare sosire a unui ţăran nou.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 100 000$
* $0 ≤ M ≤ 100.000$
* $-1 000 000 000 ≤ x, y ≤ 1 000 000 000$
* $40%$ din teste vor avea $M = 0$.
* $20%$ din teste vor avea $1 ≤ M ≤ 100$.
* Dacă un ţăran vine în sat el nu va mai pleca niciodată
* Daca aveţi nevoie de calcule de precizie se recomandă folosirea $1e-10$
h2. Exemplu
table(example). |_. terenuri.in |_. terenuri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 1
1.0 1.0
3.0 2.0
2.0 3.0
3.0 4.0
1.0 5.0
6.0 3.0
| 4
3
|
h3. Explicaţie
...
!problema/terenuri?terenuri.JPEG 70%!
În configuraţia iniţială, ţăranul $3$ va fi dominat, iar ceilalţi patru ţărani vor fi liberi.
După venirea ţăranului nou, ţăranii $2$ şi $4$ vor deveni dominaţi, iar ţăranii $1$, $5$ si cel nou venit vor fi liberi.
== include(page="template/taskfooter" task_id="terenuri") ==
