Miruna deseneaza in plan
N puncte. Ea defineste
notiunea de arbore partial pentru un set de S
puncte ca fiind o submultime de exact S-1
segmente avand capetele printre punctele date, astfel incat sa se poata ajunge
dintr-un punct in oricare altul mergand pe segmentele alese. Miruna defineste
si notiunea de arbore partial de cost minim ca fiind acel arbore partial pentru
care suma lungimilor segmentelor din submultimea aleasa sa fie minima.
Cerinta
Dupa ce deseneaza un punct
nou in plan, Miruna doreste sa afle care este suma lungimilor segmentelor ce
alcatuiesc arborele partial de cost minim pentru toate punctele desenate pana
in acel moment.
Date de intrare
Pe prima linie a fisierului
de intrare desen.in este
scris un singur numar intreg N,
reprezentand numarul de puncte desenate de Miruna. Urmatoarele N
linii vor contine cate 2 numere intregi, reprezentand coordantele unui nou punct
desenat.
Date de iesire
Fisierului de iesire desen.out
va contine N numere reale,
reprezentand suma lungimilor segmentelor ce alcatuiesc un arbore partial de
cost minim dupa fiecare punct desenat de Miruna.
Restrictii si precizari
1 <= N <= 1000
Coordonatele punctelor
vor fi numere intregi cuprinse intre 0 si 1000