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

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


Timp maxim de execuţie/test:
2 secunde
Memorie totală disponibilă/stivă:
10 MB/1 MB

În oraş tocmai s-au deschis două mall-uri, însă nu sunt tocmai apropiate. Locuitorii au înaintat o mulţime de petiţii, prin care au cerut un mijloc de transport în comun între cele două locaţii. Primarul, o persoană foarte înţelegătoare, s-a hotărât să rezolve această problemă cât mai repede cu putinţă.
Analizând harta, primarul a observat că oraşul are forma unui grid format din străzi verticale şi orizontale, distanţa dintre oricare două străzi verticale consecutive, respectiv dintre oricare două străzi orizontale consecutive fiind aceeasi. Atât străzile orizontale, cât şi străzile verticale sunt numerotate cu numere naturale consecutive, începând cu 0. O poziţie pe hartă este identificată prin două numere (x, y) unde x reprezintă numărul străzii orizontale, iar y numărul străzii verticale la intersecţia cărora se află poziţia respectivă. Unul dintre mall-uri este situat la poziţia (0,0), iar celălalt la poziţia (a,b).
Însă lucrurile nu sunt aşa de simple. Din motive de buget, trebuie ca traseul pe care se va deplasa mijlocul de transport să fie de lungime minimă. Dar, în acelaşi timp primarul doreşte să uşureze şi accesul în oraş pentru anumite puncte cheie intermediare, diferite de cele corespunzătoare celor două mall-uri. În acest sens, a selectat N astfel de puncte intermediare distincte şi a stabilit că traseul care va uni cele două mall-uri trebuie să aibă lungime totală minimă; iar dintre traseele de lungime minimă posibile, primarul va alege un traseu care să treacă prin cât mai multe dintre cele N puncte cheie intermediare.

Cerinţă

Să se determine numărul maxim de puncte cheie intermediare prin care poate trece un traseu de lungime minimă care uneşte cele două mall-uri.

Date de intrare

Fişierul de intrare bus.in conţine pe prima linie două numere naturale separate prin spaţiu, reprezentând coordonatele a şi b. Pe linia a doua se află numărul natural N, iar pe fiecare dintre următoarele N linii se află câte două numere naturale separate prin spaţiu reprezentând coordonatele x y ale celor N puncte cheie intermediare.

Date de ieşire

Fişierul de ieşire bus.out va conţine o singură linie pe care va fi scris numărul maxim de puncte cheie intermediare prin care poate trece un traseu de lungime minimă care va uni cele două mall-uri.

Restricţii

  • 1 <= N <= 100 000
  • 0 <= a <= 2 000 000 000 şi 0 <= b <= 2 000 000 000
  • 0 <= x[i] <= a
  • 0 <= y[i] <= b
  • 20% dintre teste vor avea a <= 1 000 şi b <= 1 000
  • 50% dintre teste vor avea N <= 1 000
  • Mijlocul de transport se deplasează numai pe străzi.

Exemple

bus.in bus.out Explicaţie
10 6
4
2 1
9 2
4 5
6 3

2
Justificare: Un traseu posibil este cel din figura de mai jos
Mihail-Cosmin Piţ-Rada
Colegiul Naţional "Traian" Drobeta Turnu Severin
cosmin.pit@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la InfoOltenia 2014: interclasare, palindromuri, pariuri, dreapta, riglef
De acelaşi autor: palindromuri
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor