Fişierul intrare/ieşire:terenuri.in, terenuri.outSursăONI 2011 - Baraj
AutorAndrei Parvu, Gabriel BitisAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Terenuri

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.

Cerinţă

Să se găsească şi să se afişeze numărul ţăranilor liberi la început şi după fiecare sosire a unui ţăran nou.

Date de intrare

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.

Date de ieşire

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.

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

Exemplu

terenuri.interenuri.out
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

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content