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

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


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
32MB / 1MB

Să umbli prin cartier după un meci de fotbal este periculos şi de aceea în diverse puncte ale acestuia s-au înfiinţat centre de prim-ajutor. Cartierul poate fi considerat ca fiind un caroiaj de dimensiune NxN, nodurile caroiajului fiind puncte având coordonatele (abscisă, ordonată) din mulţimea {0, 1, ..., N-1}.
În K noduri ale caroiajului s-au înfiinţat centre de prim-ajutor. Când eşti rănit în urma unei bătăi cu suporterii echipelor adverse (bătăile au loc de asemenea numai în nodurile caroiajului) nu ai decât să te duci la cel mai apropiat centru de prim-ajutor, unde vei primi îngrijiri medicale.
În urma conflictelor recente s-a decis înfiinţarea unui nou centru de prim-ajutor. Acesta trebuie să fie plasat astfel încât să se minimizeze distanţa până la cel mai apropiat centru în cazul cel mai defavorabil. Altfel spus, maximul dintre distanţele de la un nod oarecare al caroiajului până la cel mai apropiat centru de prim-ajutor să fie minim.

Cerinţă

Scrieţi un program care să determine distanţa maximă de la un nod al caroiajului la cel mai apropiat centru de prim-ajutor, după înfiinţarea noului centru.

Date de intrare

Fişierul de intrare centru.in conţine pe prima linie două numere naturale separate prin spaţiu N şi K, cu semnificaţia din enunţ. Pe fiecare dintre următoarele K linii se află câte două numere naturale cuprinse între 0 şi N-1, separate prin spaţiu, reprezentând abscisa, respectiv ordonata câte unui centru de prim-ajutor.

Date de ieşire

Fişierul de ieşire centru.out va conţine pe prima linie un singur număr natural reprezentând distanţa maximă de la un nod al caroiajului la cel mai apropiat centru de prim-ajutor, după înfiinţarea noului centru.

Restricţii

1 ≤ N ≤ 1000
1 ≤ K < N*N

Se consideră că distanţa dintre două noduri ale caroiajului (x1, y1) şi (x2, y2) este distanţa Manhattan |x1-x2| + |y1-y2|

Exemple

centru.incentru.outExplicaţii
7 5 0 1 1 4 3 6 5 0 5 5 3 Noul centru se poate înfiinţa în nodul de coordonate (3, 3). Orice altă soluţie nu micşorează distanţa maximă până la cel mai apropiat centru de prim-ajutor în cazul cel mai defavorabil



autor: Adrian Vladu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2007: casute, harta1, imax, sir1
De acelaşi autor: castel, zidar, cover
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, 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, 2ndesc, medalion, bile6, zigzag, puncte5, 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
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
surse trimise | ajutor