Krakkói Látnivalók#405

Krakkói Látnivalók

1 másodperc
256 megabájt
Közepes

Sakurako megérkezett Krakkóba, és - mint minden más turista - szeretné meglátogatni a városban az összes látnivalót. Az a problémája, hogy a verseny hamarosan kezdődik, így sietnie kell.

Van darab látnivaló, amelyek egy-egy számpárral (az -edik látnivaló (x_i,y_i)-vel) van leírva. A jó hír az, hogy magával hozta a házikedvencét, Martelt, aki bármely hely koordinátáját -ról -ra tudja változtatni, ha x^2+y^2=a^2+b^2.

Sakurako a szállodájából indul, amely a koordinátán található, és szeretne visszatérni oda. Kéri, hogy segíts neki megtalálni a minimális út hosszának a négyzetének az értékét, amely minden helyet érint és visszatér a szállodába.

A távolság a és pontok között \sqrt{(a-x)^2+(b-y)^2}-ként van definiálva.

Bemenet

Az első sorban egy egész szám, (1\le n\le 2\cdot 10^5)  található — a pontok száma.

A második sorban darab egész szám található x_1,x_2,\dots,x_n (-10^9\le x_i\le 10^9) — a látnivalók első koordinátái.

A harmadik sorban darab egész szám található y_1,y_2,\dots,y_n (-10^9\le y_i\le 10^9) — a látnivalók második koordinátái.

Kimenet

Adj meg egy egész számot — a minimumális út hosszának négyzetének az értékét, miután bármennyi koordinátaváltoztatást alkalmaztak (lehetséges, hogy egyet sem).

Példák

1. példa

Loading
Loading

2. példa

Loading
Loading

Megjegyzés

Az első példában bizonyítható, hogy nem szükséges semmilyen koordinátát megváltoztatni. Így a pontból a pontra utazunk, amelynek távolsága \sqrt{2 \cdot 2+3 \cdot 3}=\sqrt{4+9}=\sqrt{13} mindkét irányban. Tehát a válasz 2\cdot \sqrt{13}, és ennek négyzete .

A második példában megváltoztathatjuk a második pontot -ról -re, mivel 0 \cdot 0+(-4) \cdot (-4)=0 \cdot 0+4 \cdot 4. Ezután Sakurako a -ból a -be megy - távolság, a -ből a -be - távolság, és a -ből a -be - távolság, és ugyanezt az utat teszi meg az ellenkező irányban is. Tehát a válasz (1+3+5) \cdot 2=18. Ennek négyzete .

Pontozás

  1. ( pont): x_i^2+y_i^2\le 18 minden -re;

  2. ( pont): n=1;

  3. ( pont): n\le 10;

  4. ( pont): nincsenek további korlátok.