linii

Linii

== 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") ==