.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » puncte5

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
puncte5


Timp maxim de execuţie / test:
0.7s
Memorie totala disponibilă / stivă:
128MB / 64MB

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 puncte5.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 puncte5.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 ≤ K ≤ N
• 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.

Exemple

puncte5.inpuncte5.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)

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2012: culegere, culori2, stele1, cartier, medalion, numar5, bile6, proiecte, zigzag, alune, cuburi4, optim, cifreco, patru, unuzero, sstabil, palindrom1, intersectii, copaci2, 7segmente, amedie, cutie1, drept2, gheizere, plus, poly, minerale
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, swap, tetris3, monede2, ssk
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor