핫스팟 2

핫스팟은 사람들이 일반적으로 인터넷 서비스 제공자에 연결된 라우터와 무선 근거리 통신망(WLAN)을 이용해 인터넷에 접속할 수 있는 물리적 장소이다. 대부분의 사람들은 이런 장소를 "와이파이 핫스팟"이라고 부른다. 공공 핫스팟은 보통 무선 액세스 포인트, 줄여서 AP로부터 만들어진다. 구체적으로 핫스팟은 AP가 설치된 곳으로부터 거리 r 이내의 영역이다. 즉, AP의 위치를 중심으로 하고 반지름이 r인 원이다.

어떤 도시에 길고 곧은 도로가 하나 있다. AP들은 이미 도로를 따라 설치되어 있다. 시 당국은 핫스팟의 반지름을 정해야 한다. 이때 서로 다른 두 AP로부터 만들어진 핫스팟은 겹치지 않아야 하지만, 경계에서는 만날 수 있다. 특별한 경우로, 어떤 핫스팟의 반지름이 0이고 다른 핫스팟이 그 핫스팟을 내부에 포함하면 두 핫스팟은 겹치는 것이므로 이렇게 되어서는 안 된다. 하지만 반지름이 0인 핫스팟이라도 다른 핫스팟의 경계에 닿을 수는 있다.

시 당국은 핫스팟의 반지름을 정해 커버리지 영역이 최대한 커지도록 하려고 한다. 따라서 핫스팟 넓이의 합, 간단히 말해 핫스팟 반지름의 제곱의 합을 최대화해야 한다. 목표를 달성하기 위해 일부 핫스팟의 반지름은 0으로 정해질 수 있다.

도로는 평면 위의 직선으로 간주하고, 도로에 설치된 AP의 위치는 직선 위의 점이다. 직선 위의 n개의 점이 주어질 때, 핫스팟이 겹치지 않으면서 핫스팟 반지름의 제곱의 합을 최대화하는 반지름을 구하는 프로그램을 작성하시오.

예를 들어 위 그림에는 0, 2, 5에 각각 위치한 세 개의 AP가 있다. 후보로 파란색 핫스팟과 빨간색 핫스팟이 주어졌다. 파란색 핫스팟의 반지름은 왼쪽부터 1, 1, 2이다. 그러면 반지름의 제곱의 합은 6이다. 하지만 빨간색 핫스팟의 반지름은 왼쪽부터 2, 0, 3이다. 따라서 반지름의 제곱의 합은 13이며, 이것이 최댓값이다.

프로그램은 표준 입력에서 입력을 읽는다. 입력은 정수 n (2 ≤ n ≤ 300,000)이 포함된 한 줄로 시작한다. 여기서 n은 AP의 개수이다. 두 번째 줄에는 AP의 위치를 나타내는 n개의 서로 다른 정수가 증가하는 순서로 공백을 사이에 두고 주어지며, 정수는 0과 109 사이이다.

프로그램은 표준 출력에 출력한다. 정확히 한 줄을 출력한다. 그 줄에는 핫스팟 반지름의 제곱의 합의 최댓값인 음이 아닌 정수가 있어야 한다.