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