Nosaukums
Vektoru svars (vektsv)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Vektorus plaknē var apzīmēt ar skaitļu pāri (X,Y). Šos skaitļus sauc par vektora koordinātēm.

Divu vai vairāku vektoru summa ir vektors, kura katra koordināte tiek aprēķināta kā visu vektoru attiecīgo koordināšu summa. Piemēram, (1,2)+(3,4)+(5,6) = (1+3+5,2+4+6)=(9,12) .

Vektora (x,y) svaru aprēķina kā x*x+y*y.

Uzrakstiet programmu, kas N dotiem plaknes vektoriem atrod tādu šo vektoru apakškopu, ka šo vektoru summas svars ir lielākais iespējamais!

Piezīme: Lietojiet 64-bitu veselo skaitļu tipu (int64 Paskālā vai long long valodā C)!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dots naturāls skaitlis N (1≤N≤ 30000) - vektoru skaits.

Katrā no nākošajām N faila rindām dots pa diviem veseliem skaitļiem X un Y, kas atdalīti ar tukšumsimbolu - viena vektora koordinātēm. Zināms, ka visiem vektoriem šie skaitļi ir robežās -30000≤X,Y≤30000 un neviens no dotajiem nav nulles vektors (0,0).


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens naturāls skaitlis - lielākais iespējamais vektoru summas svars.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
9
0 1
6 8
0 -1
0 6
-1 1
-1 2
5 -4
1 0
6 -5
Stdout
360

Stdin
5
5 -8
-4 2
4 -2
2 1
-6 4
Stdout
202

Stdin
4
1 4
-1 -1
1 -1
-1 4
Stdout
64

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.