Fişierul intrare/ieşire:puncte1.in, puncte1.outSursăONI 2012 baraj gimnaziu
AutorDana LicaAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Puncte1 (baraj gimnaziu)

Se consideră N puncte distincte în planul definit de sistemul cartezian XOY. Fiecare punct este definit prin două numere naturale nenule reprezentând abscisa, respectiv ordonata sa. În plan putem trasa oriunde un pătrat cu laturile paralele cu axele sistemului, având lungimea laturii un număr natural nenul.

Cerinţă

Scrieţi un program care determină lungimea minimă a laturii unui pătrat care poate fi trasat, astfel încât acesta să includă cel puţin K puncte dintre cele N puncte date.

Date de intrare

Fişierul de intrare puncte1.in conţine pe prima linie perechea de numere naturale N şi K, reprezentând numărul de puncte din plan, respectiv numărul minim de puncte care trebuie să fie în interiorul pătratului de latură minimă. Pe următoarele N linii se află câte două numere naturale, x şi y, separate printr-un spaţiu, reprezentând, în această ordine, abscisa şi ordonata fiecăruia dintre cele N puncte.

Date de ieşire

Fişierul de ieşire puncte1.out conţine pe prima linie un număr natural nenul, ce reprezintă lungimea minimă a laturii determinate.

Restricţii

  • 2 ≤ N ≤ 32 000
  • 2 ≤ KN
  • 1 ≤ xi ≤ 5 000 şi 1 ≤ yi ≤ 5 000, pentru orice 1 ≤ i ≤ N
  • Un punct aflat pe oricare latură a pătratului, sau în oricare vârf, se consideră inclus în pătrat.

Exemplu

puncte1.inpuncte1.outExplicaţii
7 4
3 2
1 1
1 2
4 3
3 4
6 6
5 2
2
Pătratul cu colţul stânga jos în punctul (3,2) şi latura 2 conţine 4 puncte şi anume:
(3,2), (4,3), (3,4) şi (5,2)
Trebuie sa te autentifici pentru a trimite solutii. Click aici