Mădălina este înnebunită după probleme de geometrie. De data aceasta ea are N puncte de coordonate reale în plan şi doreşte să acopere punctele cu cercuri care au centrele pe axa OX (axa absciselor) astfel încât suma ariilor cercurilor să fie minimă.
Cerinţă
Cunoscând coordonatele celor NN puncte în plan, găsiţi o acoperire a acestor puncte cu cercuri ce au centrele aflate pe axa OX, astfel încât suma ariilor cercurilor să fie minimă.
Date de intrare
Pe prima linie a fişierului de intrare acerc.in se va afla numărul natural N. Următoarele N linii vor conţine fiecare câte două numere reale X şi Y, separate prin spaţiu, reprezentând coordonatele punctelor.
Date de ieşire
Pe prima linie a fişierului de ieşire acerc.out veţi afişa un singur număr reprezentând suma minimă a ariilor cercurilor ce respectă condiţia din cerinţă.
Restricţii
• 1 ≤ N ≤ 300
• Valorile coordonatelor punctelor vor fi în intervalul [-10 000, 10 000]
• Un cerc acoperă toate punctele din plan aflate faţă de centrul acestuia la o distanţa mai mică sau egală cu raza cercului.
• Diferenţa maximă cu care rezultatul final poate varia faţă de cel corect este de 0.001
Exemple
acerc.in
acerc.out
Explicaţii
7
0 2
1 1
1 3
4 0
3.9 2
8 4
7 4
79.6208
Se vor acoperi cele 7 puncte cu două cercuri: unul cu centrul în punctul (0, 1) şi raza egală cu 3 şi unul cu centrul în punctul (0, 7.41341) şi raza egală cu 4.04278