Lecture Screens

Many lecture halls show the same slides on several displays at once, so that a pillar or the head of the person in front of you cannot completely block your view. How much of the presented content you actually see depends on where you sit.

We model this as follows. We ignore people's heads and consider only architectural obstruction. The lecture hall is given as a closed, simple polygon (its walls do not cross). You are also given several screens as line segments in the plane, together with your own position inside the polygon.

Every screen shows the same content, running from its left endpoint (0% of the content) to its right endpoint (100%). From your position you may see all, part, or none of a given screen. Taking the union of everything you can see, we want the total fraction of the content you get. For example, if you see the left half of one screen and the right half of another, you see 100%; if you see only the left half of both, you see just 50%.

A screen can only be read from its front. Each screen is directed from its left endpoint to its right endpoint; if you view it from behind (its right side appears on your left), you see none of its content.

In the illustration, the thick lines are the walls of the hall. The arrows are the screens and point from their left to their right side. The gray regions are your view cone, and where a cone meets an arrow is the part of that screen you can see. The screen below the viewer faces the wrong way, so it is not visible. In this example you can see 90% of the content (everything except the leftmost 10%).

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

The first line contains $n$, $m$, $x$, $y$, where $3 \le n \le 100$ is the number of corner points of the polygon, $1 \le m \le 20$ is the number of screens, and $(x, y)$ is your seating position ($x$ and $y$ are real numbers).

The next $n$ lines each contain two real numbers $x_i$ and $y_i$, the $i$-th corner of the hall. There is a wall from $(x_i, y_i)$ to $(x_{i+1}, y_{i+1})$ for every $i$, and a wall from $(x_n, y_n)$ back to $(x_1, y_1)$.

The following $m$ lines each contain four real numbers $\ell x_j$, $\ell y_j$, $rx_j$, $ry_j$: the coordinates of the left endpoint $(\ell x_j, \ell y_j)$ and the right endpoint $(rx_j, ry_j)$ of the $j$-th screen.

For each data set, first print a line "Data Set x:", where $x$ is its number (starting from 1). Then print the percentage of the content you can see, rounded to two decimal places, followed by a percent sign.