Programozás‎ > ‎Feladatok‎ > ‎

Minimális skalárszorzat

Adott két vektor v1=(x1,x2,...,xn) és v2 = (y1,y2,...,yn). A két vektor skalárszorzata egyetlen szám: x1*y1+x2*y2+...+xn*yn.

Tegyük fel, hogy a vektorok koordinátáit szabadon permutálhatjuk (tetszőleges sorrendben írhatjuk). Határozzuk meg az így kapható minimális skalárszorzatot.

Feladat

Írjunk programot, ami megadja a skalárszorzat lehetséges értékei közül a minimálisat.

Bemenet

A bemenet első sora a tesztesetek T számát tartalmazza. (1 <= T <= 1000). Ezután T teszteset következik, három-három sorban kódolva. Az első sor n értékét adja meg (1 <= n <= 800), majd az xi és yj koordináták következnek, egy-egy sorban, szóközökkel elválasztva (-100000 <= xi, yj <= 100000).

Kimenet

A kimenet T sort tartalmaz, mindegyik sorban a megfelelő tesztesetre kapható minimum szerepel.

Példa

Bemenet  Kimenet
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
Case #1: -25
Case #2: 6


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2008 1A (online tesztelő)
Algoritmusok: mohó algoritmus

megoldás