냄새를 피하는 길

월드 캠프가 진행될수록 씻지 않아 냄새를 풍기는 사람이 늘고 있다. 당신은 교실 안에서 시작 지점에서 목적지까지 이동할 때, 냄새나는 사람들이 앉아 있는 자리로부터 가능한 한 멀리 떨어진 경로를 선택하려고 한다.

교실은 정수 좌표로 이루어진 직사각형 격자로 표현된다. 교실의 가로 크기와 세로 크기를 각각 Wx, Wy라고 하자. 냄새나는 사람이 앉아 있는 좌표 (x, y), 시작 지점 (sx, sy), 목적지 (tx, ty)는 모두 다음 조건을 만족한다.

• 1 <= x, sx, tx <= Wx
• 1 <= y, sy, ty <= Wy
• 2 <= Wx, Wy <= 1,000
• 냄새나는 사람의 수 n은 1 <= n <= Wx * Wy - 2 이다.

한 번의 이동으로 현재 점에서 가로 또는 세로 방향으로 1만큼 움직일 수 있다. 이동 중에는 항상 교실 안의 양의 정수 좌표에 있어야 한다. 시작 지점에서 목적지까지 이렇게 이동하며 지나간 정수 좌표들의 집합을 하나의 경로라고 하자.

어떤 경로와 냄새나는 사람들 사이의 거리는, 그 경로 위의 점 하나와 냄새나는 사람이 앉아 있는 점 하나를 고를 때 가능한 유클리드 거리 중 최솟값이다. 가능한 모든 경로 중 이 최솟값을 최대화하는 경로를 최적 경로라고 한다.

시작 지점, 목적지, 냄새나는 사람들이 앉아 있는 위치가 주어졌을 때, 최적 경로와 냄새나는 사람들 사이의 거리의 제곱을 구하라.

첫째 줄에 교실의 크기를 나타내는 두 정수 Wx, Wy가 주어진다.

둘째 줄에 시작 지점과 목적지의 좌표를 나타내는 네 정수 sx, sy, tx, ty가 주어진다.

셋째 줄에 냄새나는 사람의 수 n이 주어진다.

다음 n개의 줄에는 냄새나는 사람이 앉아 있는 좌표 xi, yi가 한 줄에 하나씩 주어진다. 시작 지점과 목적지에는 냄새나는 사람이 앉아 있지 않다.

최적 경로로 이동할 때, 냄새나는 사람들과 그 경로 사이의 거리의 제곱을 첫째 줄에 출력한다. 어떤 경로를 선택해도 냄새나는 사람이 있는 위치를 지나야 한다면 0을 출력한다.