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

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


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

În comuna Triunghi din România sunt n ţărani codificaţi prin numerele 1, 2, ..., n. După anul 1990 a început retrocedarea suprafeţelor de pământ deţinute înainte de colectivizare. Fiecare ţăran are un document prin care dovedeşte că este proprietar pe o singură suprafaţă de teren de formă triunghiulară. Din păcate, documentele dau bătaie de cap primarului (care se ocupă de retrocedarea suprafeţelor de pământ), pentru că sunt porţiuni din suprafeţele de pământ care se regăsesc pe mai multe documente.
În această comună există o fântână cu apă, fiind posibil ca ea să fie revendicată de mai mulţi ţărani. O suprafaţă de pământ este dată prin coordonatele celor trei colţuri, iar fântâna este considerată punctiformă şi dată prin coordonatele punctului.

Cerinţă

Să se scrie un program care să determine:
a) Codurile ţăranilor care au documente cu suprafeţe de pământ ce conţin în interior sau pe frontieră fântâna.
b) Codul ţăranului ce deţine un document cu suprafaţa de teren, care include toate celelalte suprafeţe.

Date de intrare

Fişierul de intrare triunghi.in are pe prima linie numărul n de ţărani, pe următoarele n linii câte 6 valori numere întregi separate prin câte un spaţiu, în formatul: x1 y1 x2 y2 x3 y3, ce reprezintă coordonatele celor trei colţuri ale suprafeţei triunghiulare deţinute de un ţăran. (x1, x2, x3 abscise, iar y1, y2, y3 ordonate). Pe linia i+1 se află coordonatele colţurilor suprafeţei de teren triunghiulare deţinute de ţăranul i, i=1,2,…,n. Ultima linie a fişierului (linia n+2) va conţine coordonatele fântânii în formatul x y, cu un spaţiu între ele (x abscisă, iar y ordonată).

Date de ieşire

Fişierul de ieşire triunghi.out va conţine pe prima linie răspunsul de la punctul a), adică: numărul de ţărani care îndeplinesc condiţia din cerinţă şi apoi codurile lor (în ordine crescătoare), cu un spaţiu între ele. Dacă nu există ţărani cu condiţia din cerinţă, pe prima linie se va scrie cifra 0. Pe linia a doua se va scrie răspunsul de la punctul b), adică: codul ţăranului cu proprietatea cerută, sau cifra 0, dacă nu există un astfel de ţăran.

Restricţii

2 ≤ n ≤ 65
• coordonatele colţurilor suprafeţelor de pământ şi ale fântânii sunt numere întregi din intervalul [-3000, 3000]
• cele trei colţuri ale fiecărei suprafeţe de pământ sunt distincte şi necoliniare
• nu există doi ţărani care să deţină aceeaşi suprafaţă de pământ
• nu se acordă punctaje parţiale.

Exemple

triunghi.intriunghi.outExplicaţii
3 10 0 0 10 10 10 0 100 100 0 -100 0 0 0 10 0 0 10 10 5 2 1 2 2 La punctul a), sunt doi ţărani care deţin suprafeţe de pământ ce au în interior sau pe frontieră fântâna, cu codurile 1 şi 2.
La punctul b), ţăranul cu codul 2 deţine o suprafaţă de teren care include, suprafeţele de pământ deţinute de ceilalţi ţărani (cu codurile 1 şi 3).


autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, maxq, tric, cover, dist, munte1, promo, puncte1, role
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, 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, testament, 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, 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
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor