== include(page="template/taskheader" task_id="linii") ==
Poveste şi cerinţă...
Pentru a nu mai plictisi concurenţii cu enunţuri prea lungi şi complicate, comisia lotului vă dă următoarea problemă. Se dau $N$ puncte în plan, aflate la coordonate întregi. Se acoperă punctele cu un număr minim de linii frânte, fiecare linie satisfăcând următoarele cerinţe:
* o linie frântă trebuie să pornească dintr-un punct având coordonate întregi
* la fiecare pas linia trebuie prelungită din punctul curent $(x, y)$ într-unul din cele $3$ puncte: $(x-1,y+1)$, $(x,y+1)$, $(x+1,y+1)$.
h2. Cerinţă
Sa se determine numărul minim de linii frânte care acoperă toate punctele date.
h2. Date de intrare
Fişierul de intrare $linii.in$ ...
Fişierul de intrare $linii.in$ conţine pe prima linie un număr natural $N$, reprezentând numărul de puncte, iar următoarele $N$ linii se află câte două numere întregi $X, Y$, separate printr-un spaţiu, reprezentând coordonatele unui punct.
h2. Date de ieşire
În fişierul de ieşire $linii.out$ ...
Fişierul de ieşire $linii.out$ va conţine pe prima linie un număr natural reprezentând numărul minim de linii frânte care acoperă toate cele $N$ puncte.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300 000$
* Coordonatele celor $N$ puncte sunt numere întregi din intervalul $[0, 100 000 000]$
* Punctele nu sunt neapărat distincte; dacă sunt mai multe puncte care coincid, atunci ele se consideră acoperite simultan de aceeaşi linie frântă.
h2. Exemplu
table(example). |_. linii.in |_. linii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
1 1
6 4
3 3
3 5
5 2
| 2
|
h3. Explicaţie
...
!problema/linii?linii.JPG 70%!
== include(page="template/taskfooter" task_id="linii") ==
