시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 200 55 25 26.316%

문제

캠프가 시작된 지도 벌써 12일이 지났다.  이제 캠프의 반이 지났을 뿐인데, 학생들은 벌써 운동부족을 호소하고 있다.

선생님은 학생들에게 달리기 시합을 시키기로 결정하고, 달리기 시합에서 1등을 한 사람은 훼밀리마트에 데려가기로 했다. 적절한 운동장을 찾고 있던 중, 숙소 근처에서 널찍한 운동장을 발견했다. 그 곳에는 가느다란 기둥이 N개 꽂혀 있었다.

달리기 코스는 한 기둥에서 시작하여 다른 기둥까지 직선코스이고 코스 내에 다른 기둥이 포함되어도 상관하지 않는다. 학생들을 운동시키는 것이 이 시합의 목적이므로, 최대한 멀리 떨어져 있는 두 기둥으로 지표를 잡으려고 한다.

이 숙소에서 나가 달리기를 하고 싶다면 이 문제를 풀어야 한다. N개의 기둥의 좌표가 주어졌을 때, 가장 멀리 떨어진 두 기둥 사이의 거리의 제곱을 출력하는 프로그램을 작성하라.

입력

첫째 줄에 기둥의 개수 N(1≤N≤100,000)이 주어지고, 이어서 N줄에 걸쳐 각 기둥의 좌표를 나타내는 정수 두 개가 주어진다. 좌표의 절댓값의 범위는 50,000을 넘을 수 없다.

출력

첫째 줄에 가장 먼 기둥 사이의 거리를 제곱하여 출력한다.

예제 입력

5
1 1
5 1
3 3
2 4
6 5

예제 출력

41

힌트

출처

  • 문제를 만든 사람: xhark