acerc

Acerc

== include(page="template/taskheader" task_id="acerc") ==

Poveste şi cerinţă...

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ă.
 
h2. Cerinţă
 
Cunoscând coordonatele celor $N$ 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ă.

h2. Date de intrare

Fişierul de intrare $acerc.in$ ...

Pe prima linie a fisierului de intrare $acerc.in$ se va afla numărul natural $N$. Următoarele linii vor conţine fiecare câte două numere reale $X$ şi $Y$, reprezentând coordonatele punctelor.
 

h2. Date de ieşire

În fişierul de ieşire $acerc.out$ ...

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 cerintă.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 300$
* Valorile coordonatelor punctelor vor fi in intervalul $[-10 000, 10 000]$
* Un cerc acoperă toate punctele din plan aflate la o distanţa mai mică sau egală cu raza cercului faţa de centrul acestuia
* Pentru $40%$ din teste $N ≤ 50$
* Pentru $70%$ din teste $N ≤ 100$
* Diferenţa maximă cu care rezultatul final poate varia faţă de cel corect este de $0.001$
 

h2. Exemplu
table(example). |_. acerc.in |_. acerc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7
0 2
1 1
1 3
4 0
3.9 2
8 4
7 4
| 79.6208

|

h3. Explicaţie

...

Se vor acoperi cele $7$ puncte cu două cercuri: unul cu centrul în punctul $(1, 0)$ şi raza egală cu $3$ şi unul cu centrul în punctul $(7.41341, 0)$ şi raza egală cu $4.04278$.
 

== include(page="template/taskfooter" task_id="acerc") ==

4904