Fişierul intrare/ieşire:reducere.in, reducere.outSursăBaraj Tudor Vianu RMI 2015
AutorSpatarel Dan-ConstantinAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Reducere

Se dă o listă de N puncte în plan prin coordonatele lor carteziene. Fiecare dintre aceste puncte are asociată o greutate notată GP care iniţial este 1. Asupra listei de puncte se efectuează următorul tip de operaţie: se aleg două puncte diferite A şi B şi pe baza acestora se determină un al treilea punct C cu caracteristicile:
XC = (GA * XA + GB * XB) / (GA + GB)
YC = (GA * YA + GB * YB) / (GA + GB)
GC = GA + GB
iar costul acestei operaţii este GA * GB * Dist(A, B). Apoi se elimină din listă punctele A şi B şi se adaugă punctul C. Acest tip de operaţie se efectuează succesiv (de N - 1 ori) până când lista va conţine un singur punct.

Cerinţă

Determinaţi costul total minim al unei secvenţe de operaţii prin care să rămâneţi cu un singur punct în listă.

Date de intrare

Fişierul de intrare reducere.in conţine pe prima linie numărul natural N. Pe următoarele N linii sunt date cele N puncte P1, P2, ..., PN prin coordonatele lor carteziene XPi şi YPi, numere naturale, câte unul pe câte o linie.

Date de ieşire

Fişierul de ieşire reducere.out conţine un singur număr zecimal, costul total minim al unei secvenţe de operaţii prin care să rămâneţi cu un singur punct în listă, cu o precizie absolută de 10-4.

Restricţii

  • 2 ≤ N ≤ 16
  • -10 000 ≤ XPi, YPi ≤ 10 000
  • Pentru 30% din teste se garantează că 2 ≤ N ≤ 8
  • Lista poate conţine iniţial sau pe parcurs două sau mai multe puncte cu aceleaşi coordonate.

Exemplu

reducere.inreducere.out
4
0 0
0 1
1 0
1 1
2.8284

Explicaţie

Se aleg P1 şi P4 şi se obţine punctul P5 de coordonate (0.5, 0.5) cu costul ~1.4142 şi greutatea 2.
Se aleg P2 şi P3 şi se obţine punctul P6 de coordonate (0.5, 0.5) cu costul ~1.4142 şi greutatea 2.
Se aleg P5 şi P6 şi se obţine punctul P7 de coordonate (0.5, 0.5) cu costul 0.0000 şi greutatea 4.
Costul total este ~2.8284.

Trebuie sa te autentifici pentru a trimite solutii. Click aici