Hide

Problem E
Ice Floe Jumping

/problems/icefloes/file/statement/en/img-0001.jpg
Photo by rubyblossom

Two polar bears (of opposite genders) were floating around on ice floes (“isflak” in Swedish, “ľadová kryha” in Slovak) somewhere outside the northern parts of Greenland, and had finally decided to meet. After only a couple of minutes, and a few jumps between ice floes, the small ice floe one of the bears jumped to sank into the freezing water, along with the bear standing on it. Luckily, the bear survived, and eventually the two bears made a couple and got many small and cute polar bear cubs.

Unlike polar bears, human scientists would probably not survive falling into the arctic waters, and they would have to compensate the lack of bear fur using intelligently written software to run on their PDAs, which can help them avoid stepping on smaller (and therefore more dangerous) ice floes than necessary. The scientists already have software and hardware to download high resolution up-to-date satellite photos of the area they will be in, and to transform the downloaded pictures into two dimensional polygons describing the shapes of the ice floes. You have been asked to write the software that given these descriptions, and the positions of the scientists, calculates the area of the smallest ice floe any of the scientists need to pass, including the ice floes the scientists are already standing on, so that they can meet.

The scientists can only jump between two ice floes if they are closer to each other than some distance $d$. Actually, it is possible to jump between two floes if there exists one pair of points, one on each ice floe, on the surfaces or borders of the floes, that are not farther away from each other than the distance $d$.

Even though the ice floes are floating around in the water, the relative positions of the ice floes can be considered constant during the time it takes for the scientists to meet. The ice floes are guaranteed to neither touch nor overlap each other.

Input

The input starts with the number of test cases $N$ on a line by itself. For each test case the following information then follows: One line with the number of ice floes $(1 \leq f \leq 100)$ and the maximum distance $(0 < d \leq 1\, 000)$ that the scientists are able to jump. $d$ is a floating point number with maximum 4 decimals. After that, one line with the coordinates of the two scientists. The coordinates are given on the form $(x\; y)$. Then follow $f$ lines with ice floe descriptions. An ice floe is described as a polygon. Every floe line consists of the number of vertices $(3 \leq v \leq 100)$ followed by $v$ coordinates, also on the form $(x\; y)$. The coordinates might be given in clockwise or counterclockwise order.

All coordinates in this problem are integers with absolute value at most $20\, 000$.

Output

For each test case, output the surface area of the smallest ice floe any of the scientists need to pass in order for them to meet, provided that they have chosen the safest possible route. If no possible route exists, output “Scientists cannot meet”. The output for each test case should be on a line by itself.

The output is considered correct if it is within relative or absolute error $10^{-7}$.

\includegraphics[width=14cm]{iceflakes_figure}
Figure 1: Illustration of the sample input
Sample Input 1 Sample Output 1
1
7 1
(2 2) (12 13)
6 (6 2) (8 4) (8 6) (7 7) (4 7) (4 5)
6 (8 7) (10 6) (13 9) (11 11) (10 10) (8 10)
6 (12 5) (24 5) (23 14) (17 13) (13 11) (14 8)
3 (10 12) (11 15) (14 12)
4 (4 10) (7 9) (10 13) (4 14)
3 (4 9) (5 8) (3 7)
5 (0 4) (3 3) (5 2) (6 0) (0 0)
6.0

Please log in to submit a solution to this problem

Log in