Fișierul intrare/ieșire puncte1.in, puncte1.out Sursă ONI 2012 baraj gimnaziu
Autor Dana Lica Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 131072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in puncte1.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii