Un vector se poate reprezenta
în plan ca o pereche (X, Y).
Suma a doi sau mai multi vectori este un vector ale carui coordonate sunt sumele
coordonatelor corespondente din vectorii care se aduna.
De exemplu
(1, 2)+(3, 4)+(5, 6) = (1+3+5, 2+4+6) = (9, 12)
Ponderea unui vector (X,
Y) este definita ca X*X+Y*Y.
Se considera N vectori în
plan.
Cerinta
Scrieti un program care sa determine o submultime de vectori dintre cei N
dati astfel încât ponderea sumei vectorilor din submultime sa fie maxima.
Date de intrare
Prima linie a fisierului de intrare vectori.in
contine un numar natural N, care
reprezinta numarul de vectori. Fiecare dintre urmatoarele N
linii contine descrierea unui vector, ca o pereche de numere întregi separate
printr-un spatiu X Y.
Date de iesire
Fisierul de iesire vectori.out
contine ponderea sumei vectorilor din submultime (maxima).
Restrictii si precizari
1<=N<=30 000
-30 000 <=X, Y <= 30 000
Nici unul dintre vectori
nu va fi (0, 0)
Utilizati în calcule întregi pe 64
de biti
Exemple
vectori.in
vectori.out
vectori.in
vectori.out
vectori.in
vectori.out
5
5 -8
-4 2
4 -2
2 1
-6 4
202
4
1 4
-1 -1
1 -1
-1 4
64
9
0 1
6 8
0 -1
0 6
-1 1
-1 2
5 -4
1 0
6 -5
360
prof. Marinel
Serban
Liceul de Informatica "Gr. C. Moisil" Iasi
e-mail: marinel_serban@yahoo.com