Fişierul intrare/ieşire:linii.in, linii.outSursăLot Botosani 2012 - Baraj 2 Seniori
AutorAlexandru CazacuAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inlinii.out
5
1 1
6 4
3 3
3 5
5 2
2

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?