전기공학

전기공학자는 전기·전자 장치가 어떻게 만들어지고 서로 어떻게 통신하는지를 연구한다. 그중에서도 무선 네트워크는 인기 있는 주제다. 이 문제에서는 어떤 구역에 무선 신호를 제공하는 상황을 단순화한 모형을 다룬다.

구역은 꼭짓점을 차례로 나열해 정의한 다각형이며, 다각형의 각 변은 벽 역할을 한다. 구역 안(또는 주변)에는 하나 이상의 무선 공유기(라우터) 가 놓여 있다. 신호 세기는 다음과 같이 정한다.

• 라우터와 어떤 위치를 잇는 선분 위에 벽이 있으면, 그 라우터는 해당 위치에 신호를 전혀 주지 못한다(세기 $0$).
• 벽이 없으면, 그 라우터가 주는 신호 세기는 $1/d^2$ 이다. 여기서 $d$ 는 라우터와 위치 사이의 거리다.
• 한 위치가 여러 라우터로부터 신호를 받으면, 그중 가장 센 신호만 센다.

여러 개의 질의 위치에 대해 최종 신호 세기를 구하라.

이 모형은 벽에 의한 신호 반사와 벽을 통과하는 투과는 무시한다.

첫 줄에 데이터 집합의 개수를 나타내는 정수 $K \ge 1$ 이 주어진다. 이어서 각 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 세 정수 $n$, $r$, $p$ 가 주어진다. 각각 다각형 꼭짓점의 수, 라우터의 수, 신호 세기를 구할 질의 점의 수이며, 세 값 모두 $1$ 이상 $100$ 이하이다.

• 다음 $n$ 줄에는 각 꼭짓점이 두 실수 $x$ $y$ 로, 다각형을 따라가는 순서대로 주어진다.
• 다음 $r$ 줄에는 각 라우터의 위치가 $x$ $y$ 로 주어진다.
• 마지막 $p$ 줄에는 각 질의 점의 위치가 $x$ $y$ 로 주어진다.

다음을 가정해도 된다. (1) 어떤 라우터나 질의 점도 벽 위에 정확히 놓이지 않는다. (2) 라우터와 질의 점이 같은 위치에 있지 않는다. (3) 라우터에서 질의 점으로 잇는 선분은 벽에 단순히 스치지 않는다. 즉, 벽을 확실히 가로지르거나 완전히 피한다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$ 는 데이터 집합의 번호이며 $1$ 부터 시작한다. 그다음 $p$ 개의 질의 점 각각에 대해, 그 점에서의 최대 신호 세기를 소수 둘째 자리까지 반올림하여 한 줄에 하나씩 출력한다.