Pagini recente » Diferente pentru problema/gminmax intre reviziile 5 si 4 | Diferente pentru problema/secv7 intre reviziile 4 si 5 | Diferente pentru problema/numerex intre reviziile 13 si 1 | Diferente pentru problema/infinitepatternmatching intre reviziile 13 si 12 | Diferente pentru problema/palmieri intre reviziile 1 si 2
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="palmieri") ==
Poveste şi cerinţă...
Pe o insulă tropicală, există cu o plajă cu $N$ palmieri. Pentru simplitate, vom considera ţărmul axa Ox, plaja fiind semiplanul punctelor cu ordonata pozitivă, iar oceanul semiplanul opus. Palmierii sunt reprezentaţi prin nişte puncte de coordonate întregi. Laura doreşte să cumpere mai multe proprietăţi cu laturile paralele cu axele de coordonate, fiecare să nu depăşească aria $A$ şi toate să aibă deschidere la ocean. Mai mult, ea şi-ar mai dori ca toţi cei $N$ palmieri să intre în proprietatea ei. Bineînţeles, Laura doreşte ca proprietăţile cumpărate să nu se intersecteze pentru a nu plăti de mai multe ori acelaşi teren. Aflaţi numărul minim de proprietăţi care trebuie achizitionate, respectând condiţiile de mai sus.
h2. Date de intrare
Fişierul de intrare $palmieri.in$ ...
Fişierul de intrare $palmieri.in$ contine pe prima linie două numere întregi $N$ şi $A$. Pe următoarele $N$ linii se găsesc câte două numere $x$ si $y$, reprezentând coordonatele palmierilor.
h2. Date de ieşire
În fişierul de ieşire $palmieri.out$ ...
În fişierul de ieşire $palmieri.out$ se găseşte un singur număr întreg ce corespunde numărului minim de proprietăţi ce îndeplineşte condiţiile.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 250 000$
* $1 ≤ A ≤ 10^9^$
* $1 ≤ x, y ≤ 10^9^$
* Pentru 30% din teste, $N ≤ 5 000$
* Pentru alte 30% din teste, $N ≤ 50 000$
h2. Exemplu
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
