| Fişierul intrare/ieşire: | linii.in, linii.out | Sursă | Lot Botosani 2012 - Baraj 2 Seniori |
| Autor | Alexandru Cazacu | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Linii
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).
Cerinţă
Sa se determine numărul minim de linii frânte care acoperă toate punctele date.
Date de intrare
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.
Date de ieşire
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.
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ă.
Exemplu
| linii.in | linii.out |
|---|---|
| 5 1 1 6 4 3 3 3 5 5 2 | 2 |
Explicaţie
