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

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


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

Să considerăm un poligon monoton cu N vârfuri.
Un poligon se numeşte monoton dacă orice paralelă la axa OY intersectează poligonul în cel mult două puncte.
Dorim să trasăm un segment care să îndeplinească simultan următoarele condiţii:
1. este paralel cu axa OY;
2. are lungimea D;
3. ambele extremităţi ale segmentului aparţin poligonului.

Cerinţă

Scrieţi un program care să determine în câte moduri putem construi un segment care să îndeplinească condiţiile din enunţ.

Date de intrare

Fişierul de intrare monoton.in conţine pe prima linie doua numere naturale separate prin spaţiu N D, cu semnificaţia din enunţ. Pe următoarele N linii sunt descrise cele N vârfuri ale poligonului, câte un punct pe o linie. Fiecare punct este specificat prin două numere întregi separate prin spaţiu x y, reprezentând abscisa şi ordonata punctului respectiv. Vârfurile poligonului sunt specificate în ordinea parcurgerii acestuia în sens trigonometric.

Date de ieşire

Fişierul de ieşire monoton.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de posibilităţi de a construi segmentul care îndeplineşte condiţiile din enunţ. Dacă există o infinitate de posibilităţi de a construi segmentul, se va afişa pe prima linie cuvântul infinit (cu litere mici).

Restricţii

• 3 ≤ n ≤ 100000
• 1 ≤ d ≤ 108
• -108 ≤ x, y ≤ 108


Exemple

monoton.inmonoton.out
5 10 -10 9 -5 -8 -3 -2 7 -9 10 -10 2

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2011: cos, avioane, obstacole, echilibru1, dag, robotel, punctfix, broscute
De acelaşi autor: celule, scp, vedete, film, ab, supertri, 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, 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, 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, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Software recomandat
surse trimise | ajutor