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

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


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

Sã considerãm N puncte distincte în plan, specificate prin coordonatele lor carteziene (abscisã, ordonatã). Punctele sunt numerotate de la 1 la N.
Selectând 3 puncte dintre acestea N obtinem un supertriunghi dacã numãrul de puncte incluse în interiorul triunghiului care are drept vârfuri cele 3 puncte selectate contine un numãr maxim de puncte dintre cele N.
Dacã un punct se aflã pe o laturã a triunghiului se considerã cã el este în interiorul triunghiului.

Cerinţă

Scrieti un program care sa determine un supertriunghi.

Date de intrare

Fisierul de intrare supertri.in contine pe prima linie un numãr natural N reprezentând numãrul de puncte. Pe urmãtoarele N linii sunt specificate cele N puncte, câte un punct câte o linie. Mai exact, pe linia i+1 se aflã douã numere naturale separate prin spatiu reprezentând abscisa, respectiv ordonata punctului i.

Date de ieşire

Fisierul de iesire supertri.out va contine douã linii. Pe prima linie va fi scris un numãr natural reprezentând numãrul maxim de puncte incluse în interiorul unui supertriunghi. Pe cea de a doua linie vor fi scrise 3 numere distincte separate prin câte un spatiu, reprezentând indicii a 3 puncte ce formeazã vârfurile unui supertriunghi.

Restricţii

  • 3 <= N <= 300
  • Abscisa si ordonata oricãrui punct sunt numere naturale <= 30000
  • Pentru orice fisier de test vor exista cel putin 3 puncte necoliniare.
  • Indicii vârfurilor supertriunghiului determinat pot fi afisate în orice ordine.

Exemple

supertri.in supertri.out
9
1 1
2 2
3 3
2 1
3 2
3 1
4 2
4 1
5 1
9
1 9 3

prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2008: celule, premii, cai, scp, forum, vedete, film, finala, ab, nice, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: celule, scp, vedete, film, ab, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre geometrie: forum, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, cuiburi, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Software recomandat
surse trimise | ajutor