Atenție! Aceasta este o versiune veche a paginii., scrisă la 2015-10-09 10:55:08.
Revizia anterioară   Revizia următoare  

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 .

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 A4 ș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.

Date de intrare

Fișierul de intrare reducere.in ...

Date de ieșire

În fișierul de ieșire reducere.out ...

Restricții

  • ... ≤ ... ≤ ...

Exemplu

reducere.in reducere.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicație

...

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii