În Hackerville există un spaţiu de joacă îndrăgit de mulţi copii. Acest spaţiu are însă unele probleme, el are nişte gropi care îi pot încurca pe copii în activităţile lor.
Conducerea oraşului vrea să acopere un număr maxim de gropi cu o suprafaţă de formă pătratică.
Cerinţă
Dându-se coordonatele relative la centrul parcului ale gropilor şi dimensiunea suprafeţei pătratice va trebui
să aflaţi numărul maxim de gropi ce pot fi acoperite.
Date de intrare
Fisierul de intrare
gropi1.in contine pe prima linie două numere întregi N şi L reprezentând numărul de gropi, respectiv lungimea laturii suprafeţei ce va fi folosită pentru acoperire. Pe următoarele N linii se afla câte două numere întregi, (xi, yi) reprezentând coordonatele gropii cu numărul i.
Date de ieşire
Fişierul de ieşire
gropi1.out va conţine pe prima linie numărul maxim de gropi ce pot fi acoperite de suprafaţa pătratică.
Restricţii
1 <=
L <= 200 000
1 <=
N <= 1 000
xi, yi sunt din intervalul [-100 000, 100 000]
Gropile se consideră punctiforme.
Pentru 20% din teste
xi, yi sunt din intervalul [-100, 100] şi 1
<= N <= 100
Pentru 50% din teste 1 <=
N <= 100
Exemplu
gropi1.in
gropi1.out
Explicatie
7 2 0 0 1 1 1 2 -1 0 -1 -1 -1 1 2 3
5
Suprafaţa acoperă gropile 1, 2, 4, 5, 6
stud. Cosmin-Dumitru Oprea
UPB, Facultatea de Automatică şi Calculatoare Bucureşti