하수도 계획

ICPC City는 빠르게 성장하는 도시이다. 인구가 급격히 늘면서 여러 공공 시설을 개선, 확장, 또는 보수해야 하는 상황에 놓였고, 그중 하나가 하수도 시스템이다. 최근 보고서에 따르면 도시를 가로지르는 새로운 하수도 간선 관로를 건설해야 한다. 현대의 하수도 시스템은 자동 제어 장치로 깨끗하게 관리되지만, 주민들은 여전히 간선 관로가 자신들로부터 가능한 한 멀리 놓이기를 원한다.

ICPC City는 잘 계획된 완전한 직사각형 모양의 도시로, 네 꼭짓점은 $L < R$, $B < T$인 어떤 값에 대해 $(L, B)$, $(L, T)$, $(R, T)$, $(R, B)$이다. 간선 관로는 양쪽의 이웃 지역을 연결해야 하므로 도시를 가로지르는 직선이어야 한다. 우리는 이 관로를 도시의 모든 사람으로부터 가능한 한 멀리 놓고자 한다. 인구는 $L \le X_i \le R$, $B \le Y_i \le T$를 만족하는 $N$개의 점 $P_i = (X_i, Y_i)$의 집합으로 주어진다.

도시 영역을 지나는 임의의 직선 $l$에 대해 다음 목적 함수를 정의한다.

$\delta(l) = \min_{i = 1, \dots, N} d(P_i, l),$

여기서 $d(P_i, l)$은 점 $P_i$에서 직선 $l$까지의 유클리드(수직) 거리이다. 즉 $\delta(l)$은 모든 $P_i$에서 직선 $l$까지의 거리 중 최솟값이다.

그림 1. 도시 영역을 지나는 직선 $l$에 대한 $\delta(l)$의 계산 방법.

최적의 간선 계획은 꼭짓점이 $(L, B)$, $(L, T)$, $(R, T)$, $(R, B)$인 직사각형과 교차하는 모든 직선 $l$ 중에서 $\delta(l)$을 최대로 하는 직선 $l^*$이다. 그림 2는 최적 계획 $l^*$의 세 가지 기본 경우를 보여 준다.

그림 2. 세 가지 기본 예시.

$L$, $R$, $B$, $T$와 $N$개의 점 $P_i$가 주어질 때, 최적 간선 계획 $l^*$에 대한 값 $\delta(l^*)$을 구하는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $K$ $(1 \le K \le 20)$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫째 줄에는 도시 영역을 정의하는 네 실수 $L$, $R$, $B$, $T$ $(-1000 \le L < R \le 1000;\ -1000 \le B < T \le 1000)$가 주어진다. 다음 줄에는 점의 개수 $N$ $(1 \le N \le 500)$이 정수로 주어진다. 이어지는 $N$개의 줄에는 각각 점 $P_i$의 $X$좌표와 $Y$좌표인 두 실수 $X_i$, $Y_i$가 주어지며, $L \le X_i \le R$, $B \le Y_i \le T$를 만족한다.

모든 실수는 소수점 아래 정확히 세 자리로 주어지고, 한 줄에서 인접한 두 수는 하나의 공백으로 구분된다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 최적 간선 계획 $l^*$에 대한 값 $\delta(l^*)$을 정확히 한 줄에 출력한다. 값은 소수점 아래 정확히 세 자리로 반올림하여 출력한다.