Fişierul intrare/ieşire:acerc.in, acerc.outSursăLot Alba Iulia 2010, Baraj 2
AutorCosmin GheorgheAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inacerc.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content