| Fişierul intrare/ieşire: | acerc.in, acerc.out | Sursă | Lot Alba Iulia 2010, Baraj 2 |
| Autor | Cosmin Gheorghe | Adăugată de |  Dragos-Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Acerc
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 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ă.
Date de intrare
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.
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 cerintă.
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
Exemplu
| acerc.in | acerc.out |
|---|---|
| 7 0 2 1 1 1 3 4 0 3.9 2 8 4 7 4 | 79.6208 |
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.
