26135번 - Islands from the Sky 스페셜 저지다국어

You might never have heard of the island group of Iceepeecee, but that suits their inhabitants just fine. Located in a remote part of the South Pacific, they are truly off the beaten track, without any regular air or sea traffic, and they have remained a tropical paradise with unspoiled local fauna and flora.

Being off the map is great when you don’t want to be overrun by hordes of tourists, but not so ideal when you actually do need a map for some reason. One such reason came up recently: Iceepeecee’s central government needs an exact map of the islands to apportion government funds. Even tropical paradises need money, so Iceepeecee needs a map!

The easiest way to create a map would be an aerial survey. After dismissing chartering planes as too expensive, building an air balloon as too dangerous, and fitting carrier pigeons with cameras as too cruel to animals, they had a brilliant idea. Even with its remote location, there are still plenty of commercial airplanes crossing the skies above Iceepeecee. What if one mounted cameras on flights that are already scheduled to fly anyway? That would be a cheap solution to the problem!

Iceepeecee’s plan is to install line-scan cameras on the planes. These cameras point straight downwards and collect images one line segment at a time, orthogonal to the flight path. The photographed line segment will be determined by the altitude that the plane is flying at, and the camera’s aperture angle θ (see Figure F.1). Greater angles θ mean that the camera can see more, but also that the camera is more expensive.

Moreover, Iceepeecee wants to make sure that each island is observed in its entirety by at least one flight. That means it is not sufficient that an island is only partially photographed by multiple flights, even if the combination of the photographs covers the whole island.

Flight paths follow straight line segments in three-dimensional space, that is, (x₁, y₁, z₁) − (x₂, y₂, z₂) (see Figure F.2), where the z-coordinates give the altitude of the plane. Photographs are taken only along these line segments.

Given the location of their islands and flights, Iceepeecee wants to find the smallest aperture angle θ that allows for a successful survey. Can you help?

Figure F.1: A view of the plane, shown head-on. Its camera points downward and can see the part of the ground underneath the plane that is shown in green. How much is visible depends on the aperture angle θ.

(a) Three islands (shown in black) and two flight paths (red and green). Altitudes are not shown.	(b) The shaded areas represent the ground visible on the two flight paths for an optimally chosen θ.
Figure F.2: Surveying three islands via two flight paths. This corresponds to the first sample input.

The input describes a set of islands and flight paths. It starts with a line containing two integers n and m, the number n of islands, and the number m of flight paths, respectively (1 ≤ n, m ≤ 100). This is followed by descriptions of the n islands. Each island description starts with a line containing a single integer ni , the number of vertices of the polygon describing the i^th island (3 ≤ n_i ≤ 100). It is followed by ni lines, each containing two integers x_ij, y_ij (|x_ij|, |y_ij| ≤ 10⁶), specifying the vertices for the i^th island in counterclockwise order. Each island’s polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. Different islands do not intersect or touch.

The input concludes with another m lines, each describing a flight path. Each such line contains six integers x₁, y₁, z₁, x₂, y₂, z₂ (|x_i|, |y_i|, |z_i| ≤ 10⁶, z_i > 0 and (x₁, y₁) ≠ (x₂, y₂)). They specify that a flight takes place from (x₁, y₁, z₁) to (x₂, y₂, z₂).

Output the smallest angle θ (in degrees) that allows for a complete survey of the islands with the given flights. The answer should be exact to an absolute or relative error of 10^-6. If there is no such angle, then output impossible. The input is chosen such that if the coordinates of the island vertices are changed by at most ±10^-8 , then the answer will not change more than the allowed rounding error.