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

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


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


Se cunosc coordonatele în plan pentru n puncte. Oricare trei puncte dintre punctele date nu sunt coliniare.

Cerinţă

Scrieţi un program care să determine numărul maxim de puncte ce pot fi alese dintre cele n date astfel încât să constituie vârfurile unui poligon convex.

Date de intrare

Fişierul de intrare select.in conţine pe prima linie numărul natural n reprezentând numărul de puncte date iniţial. Pe fiecare dintre următoarele n linii se află câte două numere reale separate cu un spaţiu, reprezentând coordonatele celor n puncte.

Date de ieşire

Fişierul de ieşire select.out va conţine o singură linie, pe care este scris un singur număr întreg, reprezentând numărul maxim de puncte care pot fi alese dintre cele n date şi care constituie vârfurile unui poligon convex.

Restricţii

  • 3 <= n <= 100
  • Toate coordonatele sunt perechi de numere reale mai mari sau egale cu 0 şi mai mici sau egale ca 1000, cu cel mult trei zecimale
  • Nu există trei sau mai multe puncte coliniare
  • Toate punctele sunt diferite între ele

Exemple

select.in select.out select.in select.out
19
0 0
40 30
1 29
1 3
20 1
28 2
3 8
4 7
38.1 24
37 25
31 29
12 5
13 6
26 5
19 4
27 7
30 10
35 19
7 28

10 7
0 0
6 3
6 6
10 3
10 6
16 0
9.000 15.0

5
prof. Lucian Ilea
Colegiul Naţional „Emil Racoviţă” Cluj-Napoca
ylucian@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: sokoban, codpatrat, puncte4
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, 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, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre geometrie: forum, supertri, 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, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
surse trimise | ajutor