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

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


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

Se dă o dreaptă de forma y = a care se află deasupra a N segmente paralele cu axa OX.
Definim distanţa de la un punct P la un segment ca fiind distanţa minimă dintre punctul P şi orice alt punct care aparţine segmentului respectiv.

Cerinţă

Scrieţi un program care să determine punctul de pe dreapta y = a pentru care suma distanţelor la cele N segmente să fie minimă.

Date de intrare

Fişierul de intrare sdmin.in conţine pe prima linie numărul natural N reprezentând numărul de segmente. Pe linia a doua se află un numar întreg a care descrie dreapta y = a. Următoarele N linii vor conţine 3 numere întregi x1 x2 y reprezentând capetele segmentelor (x1, y), respectiv (x2, y), unde x1 <= x2.

Date de ieşire

Fişierul de ieşire sdmin.out va conţine două numere reale separate prin spaţiu, reprezentând suma minimă şi respectiv abscisa punctului din care se obţine aceasta.

Restricţii

  • 1 <= N <= 500
  • -100 000 <= a, x1, x2, y <= 100 000
  • Pentru 20% din teste se garantează că numărul de segmente împreună cu coordonatele acestora sunt cuprinse între 0 şi 50.
  • Se consideră corectă orice soluţie în care suma minimă diferă cu cel mult 10-4 faţă de rezultatul corect.
  • Se recomandă folosirea tipului de date double.
  • Dacă există mai multe puncte pentru care se obţine suma minimă se poate afişa oricare dintre acestea.
  • Distanţa dintre două puncte (x1, y1), (x2, y2) este egală cu sqrt((x1-x2)2+(y1-y2)2).

Exemplu

sdmin.in sdmin.out
4
3
3 5 0
8 11 1
13 14 1
18 20 2
18.167617 12.090860
Alexandru Cazacu
Universitatea Bucureşti - Facultatea de Matematică şi Informatică
alexandru.cazacu92@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
De acelaşi autor: ripstick, triunghi5, descompunere, vectori1, drumuri2
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, testament, jb, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
surse trimise | ajutor