Fişierul intrare/ieşire:pachete.in, pachete.outSursăpreONI 2007, Runda 1
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Pachete

Zaharel si-a facut firma de curierat si trebuie sa transporte cate un pachet fiecaruia din cei N clienti din oras. Orasul in care locuieste Zaharel este foarte asemanator cu Manhattan, in sensul ca te poti deplasa doar pe directiile nord-sud si est-vest. De asemenea, fiecare client, cat si sediul firmei, poate fi reprezentat printr-un punct in plan. Fiecare pachet trebuie livrat cat de repede posibil, astfel incat livrarea pachetelor se va face mereu pe un drum de distanta (Manhattan) minima. Deoarece predarea pachetului unui client se face foarte repede, pe drumul catre un client, Zaharel poate alege sa livreze pachete si altor clienti, cu conditia sa se pastreze distanta minima.
Stiind locatia sediului si a celor N clienti, determinati numarul minim de drumuri pe care trebuie sa le faca Zaharel pentru a livra toate pachetele.

Date de intrare

In fisierul pachete.in se afla pe prima linie numarul natural N reprezentand numarul de clienti. A doua linie va contine doua numere naturale Ox Oy reprezentand coordonatele x, respctiv y a sediului firmei. Urmeaza N linii fiecare continand doua numere naturale Xi Yi, reprezentand coordonatele clientilor.

Date de iesire

Fisierul de iesire pachete.out va contine o singura linie pe care se va afla numarul minim de drumuri pe care trebuie sa le faca Zaharel.

Restrictii

  • 1 ≤ N ≤ 50.000
  • Distana Manhattan dintre doua puncte (x1,y1) si (x2,y2) este |x1-x2|+|y1-y2|
  • Toatele cele N puncte, cat si sediul firmei, au coordonatele x diferite doua cate doua, cat si coordonatele y
  • 0 ≤ xi, yi ≤ 2*109

Exemplu

pachete.inpachete.out
4
0 3
1 2
2 5
3 0
4 1
3

Explicatie

Cele 3 drumuri sunt:
(0,3) -> (2,5)
(0,3) -> (1,2) -> (3,0)
(0,3) -> (4,1)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content