풀 뜯는 염소

농부 존이 목장에 풀을 뜯을 염소 $N$마리를 들였다. 염소 $i$는 위치 $P_i$에 박은 말뚝에 길이 $L_i$의 줄로 묶인다. 즉 이 염소는 점 $P_i$에서 거리 $L_i$ 이내라면 어디로든 갈 수 있고, 그 밖으로는 나가지 못한다. 목장은 넓고 평평하니 무한히 넓은 2차원 평면으로 생각하면 된다.

말뚝 위치는 지난 무리를 치던 때 정해 둔 것을 그대로 쓰고, 줄 길이만 새로 정해야 한다. 정하기 까다로운 조건이 두 가지 있다.

• 염소 전체가 물통 하나에 닿아야 한다. 물통을 어디에 놓을지는 아직 정하지 않았다. 후보는 $Q_1, Q_2, \dots, Q_M$으로 좁혔지만, 그중 어느 자리를 쓸지는 모른다.
• 염소는 성질이 고약해서 한데 모이면 요란하게 싸운다. 모두의 평온을 위해 존은 염소 전체가 닿을 수 있는 영역의 면적 $A$를 최소로 만들고 싶다.

존은 기하에 약한 탓에 이 계산만은 도움이 필요하다.

물통 위치 $Q_j$마다, 물통이 그 자리에 있을 때 염소 전체가 닿을 수 있는 영역의 면적 $A_j$가 최소가 되도록 줄 길이를 정하고, 그 면적 $A_j$를 구하라.

그림

아래 그림에서 파란 점 네 개는 말뚝 위치 $P_1, P_2, P_3, P_4$이고, 빨간 점 두 개는 물통 후보 $Q_1, Q_2$다. 색칠한 두 영역의 면적이 각각 $A_1$과 $A_2$다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $M$이 주어진다.

다음 $N$개의 줄에는 말뚝 위치 $P_1, P_2, \dots, P_N$이 한 줄에 하나씩 주어지고, 그 뒤 $M$개의 줄에는 물통 후보 $Q_1, Q_2, \dots, Q_M$이 한 줄에 하나씩 주어진다.

이 $N + M$개의 줄은 각각 해당 위치의 $x$ 좌표와 $y$ 좌표를 공백 하나로 구분해 담고 있다.

제한

• 모든 좌표는 $-1\,000$ 이상 $1\,000$ 이하의 정수다.
• 한 테스트 케이스의 $P_1, \dots, P_N, Q_1, \dots, Q_M$은 모두 서로 다르고, 그중 어느 세 점도 한 직선 위에 있지 않다.
• $1 \le T \le 5$
• $2 \le N \le 1\,000$
• $1 \le M \le 100$

각 테스트 케이스마다 Case #x: A1 A2 ... AM 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, $A_1$부터 $A_M$까지는 공백 하나로 구분한다.

각 면적은 소수점 아래 세 자리로 반올림해 출력한다. 최소 면적이 0이면 0.000을 출력한다.