Electrical Engineering

Electrical engineers study how electrical and electronic devices are built and how they communicate with one another. A popular topic is wireless networking. Here we look at a simplified model of providing wireless coverage to an area.

The area is a polygon given by a sequence of corners, and every edge of the polygon acts as a wall. Inside (or around) the area there are one or more wireless routers. Signal strength is modeled as follows.

• If a wall lies on the straight segment between a router and a location, that router gives the location no signal at all (strength $0$).
• If there is no wall, the signal strength from that router is $1/d^2$, where $d$ is the distance between the router and the location.
• If a location receives a signal from several routers, only the strongest signal is counted.

For several query locations, report the resulting signal strength.

This model ignores reflection of signals off walls and penetration through walls.

The first line contains an integer $K \ge 1$, the number of data sets. Each data set has the following form.

The first line of a data set contains three integers $n$, $r$, $p$: the number of polygon corners, the number of routers, and the number of query points. All three values are between $1$ and $100$.

• The next $n$ lines each contain a corner as two floating-point numbers $x$ $y$, listed in order around the polygon.
• The next $r$ lines each contain a router location $x$ $y$.
• The final $p$ lines each contain a query point $x$ $y$.

You may assume that (1) no router or query point lies exactly on a wall, (2) no router coincides with a query point, and (3) the segment from a router to a query point never merely touches a wall — it either properly crosses the wall or avoids it completely.

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set number, starting from $1$. Then, for each of the $p$ query points, print on a line by itself the maximum signal strength at that point, rounded to two decimal places.