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ă