점 집합의 너비

평면 위의 점 $n$개로 이루어진 집합 $S$가 있다. $S$의 너비 $w$는 $S$ 전체를 사이에 두는 두 평행선 사이 거리의 최솟값이다. 그림 1이 그 예이다.

그림 1: 점 세 개로 이루어진 집합의 너비 $w$.

그림 1에서 $S$는 점 $(0, 0)$, $(0, 3)$, $(3, 0)$ 세 개로 이루어진다($n = 3$). 너비를 결정하는 두 직선은 $\ell$과 $\ell'$이고, 둘 사이의 거리는 $w = 3\sqrt{2}/2 \simeq 2.12$이다. 이 문제에서는 입력으로 주어진 점 집합의 $w^2$의 정수부를 구해 출력한다. 그림 1이라면 $w = 3\sqrt{2}/2$이므로 $w^2 = 4.5$이고, $4.5$의 정수부인 $4$를 출력하면 된다.

문제를 푸는 데 쓸 만한 공식을 하나 준다. 세 점 $A = (x_a, y_a)$, $B = (x_b, y_b)$, $C = (x_c, y_c)$에 대해 삼각형 $ABC$의 높이 $h$(그림 2)는 다음과 같다.

$h = \sigma \frac{(x_a - x_c)(y_b - y_c) - (x_b - x_c)(y_a - y_c)}{\sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}}$

여기서 $ABC$가 반시계 방향이면(그림 2의 경우) $\sigma = 1$이고, 시계 방향이면 $\sigma = -1$이다.

그림 2: 삼각형 $ABC$.

$S$의 점이 모두 한 직선 위에 있으면 너비 $w$는 0이다.

첫 줄에 $S$에 속한 점의 개수 $n$이 주어진다. 다음 $n$개의 줄에는 점 하나의 $x$ 좌표와 $y$ 좌표가 공백 하나로 구분되어 주어진다.

좌표는 0 이상 199 이하의 정수이다. 점은 최대 100000개이고, 같은 점이 여러 번 주어질 수 있다.

$w^2$의 정수부를 출력한다.