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)²+(y1-y2)²).

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