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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 8MB

Un bătrânel are m nepoţi şi o pădure pe care vrea să o împartă în m părţi, pentru a clarifica situaţia ei prin testament. Pădurea este alcătuită din m*n pomi codificaţi prin numerele 1, 2, ..., m*n, pentru care se cunosc coordonatele în plan. Pentru a realiza o împărţire cât mai echitabilă, bătrânelul vrea să determine m suprafeţe disjuncte în formă de poligoane convexe care să conţină fiecare câte n pomi în interior sau pe frontieră. Suprafetele trebuie să aibă vârfurile în câte un pom din pădure. Codurile pomilor aflaţi pe frontiera fiecărei suprafeţe vor fi scrise în testatment, pentru a nu lăsa loc de ceartă între nepoţi.

Cerinţă

Să se scrie un program care să determine o modalitate de împărţire a pădurii cu restricţiile precizate anterior.

Date de intrare

Fişierul de intrare testament.in va conţine pe prima linie numerele n şi m, iar pe următoarele m*n linii coordonatele pomilor în ordinea codificării: abscisă ordonată.

Date de ieşire

Fişierul de ieşire testament.out va conţine m linii, fiecare dintre aceste linii conţinând: k si q urmat de k numere separate prin câte un spaţiu reprezentând codificările pomilor, care sunt vârfurile unei suprafaţe de pădure din testament date în sens trigonometric, urmate de q numere reprezentand codificările pomilor care sunt în interior sau pe marginea suprafeţei de pământ, exceptând vârfurile, pentru câte un nepot. k reprezintă numărul de vârfuri a suprafeţei de pădure, iar q reprezintă numărul de pomi din interiorul suprafeţei.

Restricţii

3 ≤ n ≤ 100
1 ≤ m ≤ 100
• Coordonatele pomilor sunt numere întregi cu valoarea absolută < 32000;
• Sensul trigonometric este invers acelor de ceasornic.
• Două suprafeţe sunt disjuncte dacă interioarele lor au intersecţia egală cu mulţimea vidă şi frontierele lor au intersecţia vidă. Pomii au poziţii distincte.
• Dacă există mai multe soluţii se va afişa una dintre ele.

Exemple

testament.intestament.outExplicaţii
4 2 6 1 4 8 2 1 3 9 2 6 6 6 3 20 0 10 4 0 6 5 3 1 3 1 2 7 8 4 Prima suprafaţă de pădure are colţurile în pomii 6, 5, 3, 1, iar cea dea doua în pomii 2, 7, 8.
A doua suprafaţă de pădure conţine în interior pomul 4.

autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la LOT SB 2011: cifre4, grad2, risipa, liste, pixy, domino2, neconex, enigma, asfalt1, intervale, lant1, lcdr, jocs, jb
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, creioane, exp, donald, young, albine, turn, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, covor, pavari, parcela, grad1, ec, stalpi2, grad2, nrpomi, elicop, triburi1, showroom, cartite
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, select, proiect, poligon4, terenuri, monoton, acoperire, capra, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
surse trimise | ajutor