Diferente pentru problema/pachete intre reviziile #5 si #12

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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 minim.
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.
h2. Date de intrare
* $1 ≤ N ≤ 50.000$
* Distana Manhattan dintre doua puncte $(x{~1~},y{~1~})$ si $(x{~2~},y{~2~})$ este $|x{~1~}-x{~2~}|+|y{~1~}-y{~2~}|$
* Toatele cele $N$ puncte, cat si sediul firmei, au coordonatele $x$ diferite doua cate doua, cat si coordonatele $y$
* $0 ≤ x{~i~}, y{~i~} ≤ 2*10^9^$
h2. Exemplu
== include(page="template/taskfooter" task_id="pachete") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1466