Se dau N puncte în plan. Acestea au coordonate reale, strict pozitive. Să se gasească, pentru fiecare punct P, triunghiul dreptunghic de arie maximă, care îndeplineşte următoarele proprietăţi:

• are unghiul drept în punctul P
• nu conţine în interior nici unul dintre punctele date (pe laturi poate)
• are catetele paralele cu axele OX, OY
• punctul P reprezintă vârful din dreapta-sus
• vârfurile se află în primul cadran (au coordonatele mai mari ca 0)

Cerinţă

Să se afişeze pentru fiecare punct, aria cerută.

Date de intrare

Fişierul de intrare triunghi.in conţine pe prima linie numărul natural N reprezentând numărul de puncte. Urmatoarele N linii, conţin cate două numere reale, X_i, respectiv Y_i, reprezentand coordonatele celor N puncte.

Date de ieşire

Fişierul de ieşire triunghi.out va conţine N linii. Pe linia i, se află aria maximă a triunghiului cerut pentru al i-lea punct din fişierul de intrare.

Restricţii

• 1 <= N <= 5 000
• 0 < X_i, Y_i <= 40 000
• Răspunsul se consideră corect dacă diferă cu cel mult 10^-4 de răspunsul comisiei.

Exemplu

triunghi.in	triunghi.out
5 1 4 2 5 1 3 1 2 4 4	2.0000 3.1250 1.5000 1.0000 8.0000

stud Alexandru Cazacu

Facultatea de Matematica si Informatică Bucuresti

infooltenia2013@gmail.com