CSES - Kanavaras II
  • Time limit: 3.00 s
  • Memory limit: 512 MB

Tiirikka-Timppa joutuu muuttamaan suunnitelmaansa. Jos hän ryöstäisi kaksi kanalaa, jotka ovat lähekkäin, poliisi voisi päätellä, että asialla on ollut sama tekijä. Timppa ei halua helpottaa poliisin tutkimuksia, ja niinpä hän päättääkin ryöstää kaksi kanalaa, jotka ovat mahdollisimman kaukana toisistaan.

Sinulle on annettu tiedot kanaloiden sijainneista, ja tehtäväsi on laskea, mikä on suurin mahdollinen etäisyys kahden kanalan välillä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: kanaloiden määrä.

Tämän jälkeen syötteessä on nn riviä, joista jokainen kertoo yhden kanalan sijainnin. Rivillä on kaksi kokonaislukua xx ja yy: kanalan koordinaatit.

Tuloste

Ohjelmasi tulee tulostaa yksi luku: suurin mahdollinen etäisyys kahden kanalan välillä neliönä.

Rajat

  • 3n1500003 \le n \le 150000
  • 109x,y109-10^9 \le x, y \le 10^9

Esimerkki

Syöte:

3
1 2
6 1
3 3

Tuloste:

26