Fișierul intrare/ieșire reducere.in, reducere.out Sursă Baraj Tudor Vianu RMI 2015
Autor Dan Spătărel Adăugată de avatar spatarel Spatarel Dan-Constantin • spatarel
Timp de execuție pe test 2 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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.in reducere.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii