상어와 함께 수영하기

라호야(La Jolla)의 한 해변에는 부두 바로 옆에 표범상어가 꽤 많이 산다. 이 상어들은 몸길이가 약 4피트로 대부분의 상어보다 훨씬 작다. 어떤 사람들은 이 상어들과 함께 물속에서 헤엄치는 것을 아주 짜릿한 경험으로 여긴다. 하지만 대회 운영진은 이것이 그리 좋은 생각이 아니며, 만약 표범상어 무리와 함께 물속에 있게 된다면 최우선 목표는 상어들로부터 최대한 멀리 떨어져 있는 것이라는 데 모두 동의한다. 다행히 (방수만 된다면) 컴퓨터가 바로 그 일을 도와줄 수 있다.

물을 정수 좌표로 이루어진 $w \times h$ 크기의 2차원 격자로 나타낸다. 시각 $1$에 당신은 점 $(1, 1)$에서 출발한다. 매 시간 단계마다 당신은 상하좌우 중 한 칸으로 헤엄쳐 이동하거나 제자리에 머무를 수 있으며, 어느 경우에도 격자 밖으로 나갈 수는 없다. 여러 시각에서의 상어 위치와 고려할 시간 구간 $t$가 주어진다. 당신은 $t$개의 시간 단계 동안 모든 상어로부터 최대한 멀리 떨어져 있도록 이동 계획을 세워야 한다.

더 정확히 말하면, 각 시간 단계에서 그 시각에 존재하는 상어까지의 거리 중 가장 가까운 값을 생각하고, 이 값들을 $t$개의 시간 단계 전체에 대해 모은 최솟값(상어에게 가장 가까이 다가간 거리)을 $d$라 하자. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 유클리드 거리 $d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$로 측정한다. 목표는 시각 $t$에 다시 위치 $(1, 1)$로 돌아오면서 $d$를 최대한 크게 만드는 이동 계획을 찾는 것이다.

첫 번째 줄에는 입력에 포함된 데이터 세트의 개수 $K \ge 1$이 주어진다. 그 뒤로 다음 형식의 데이터 세트 $K$개가 이어진다.

각 데이터 세트의 첫 번째 줄에는 네 정수 $w$, $h$, $t$, $s$가 주어진다. $1 \le w, h \le 10$은 고려하는 물 영역의 너비와 높이, $1 \le t \le 100$은 당신이 물속에 있는 시간 단계의 수, $1 \le s \le 10000$은 상어 목격 횟수이다.

그 뒤로 $s$개의 줄이 이어지며, 각 줄에는 세 정수 $x_i$, $y_i$, $t_i$ ($1 \le x_i \le w$, $1 \le y_i \le h$, $1 \le t_i \le t$)가 주어진다. 이는 시각 $t_i$에 위치 $(x_i, y_i)$에 상어가 있다는 뜻이다. 이 목격 정보들은 어떤 기준으로도 정렬되어 있지 않다.

각 데이터 세트에 대해, 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 $x$는 그 데이터 세트의 번호이다($1$부터 시작). 그다음, 가능한 최선의 이동 계획에서 상어에게 가장 가까이 다가간 거리를 소수점 아래 둘째 자리까지 반올림하여 출력한다. (출력이 $0.00$이면 어느 시점엔가 상어와 같은 칸을 차지하는 것을 피할 수 없다는 뜻이다.)