Aerial Survey Optimization

The government of the remote island group Iceepeecee needs an exact map of its islands in order to apportion funds. To do this, they plan to install line‐scan cameras on commercial flights. The camera pointed directly downward captures a line segment on the ground at each moment. The length of the photographed segment is determined by the current altitude z and the camera's aperture angle \(\theta\): specifically, at a given point the half‐length of the captured line is \(z\tan(\theta/2)\). A flight follows a straight line segment in 3D space between two waypoints \((x_1,y_1,z_1)\) and \((x_2,y_2,z_2)\). Its ground projection is the segment from \(A=(x_1,y_1)\) to \(B=(x_2,y_2)\) and the altitude at an intermediate point is obtained by linear interpolation.

The camera is fixed so that, at every point along the flight the ground area photographed is a line segment centered at the ground position of the plane, perpendicular to the flight direction, with half‐length equal to the current altitude multiplied by \(\tan(\theta/2)\). The coverage area of a flight is defined as the union over the flight of these line segments (restricted to the flight’s ground projection) and its shape is essentially a “ribbon” whose width changes along the flight.

An island is considered completely surveyed by a flight only if the entire island is contained within the coverage area of that flight. Given the positions and sizes of the islands and the details of the flight paths, your task is to determine the minimum aperture angle \(\theta\) (in radians) that allows each island to be completely observed by at least one flight.

The following geometric interpretation can be used for islands modeled as circles: an island with center \((x,y)\) and radius \(r\) is fully covered by a flight if there exists a point on the flight’s ground projection at which the camera’s capture half‐length, \(z\tan(\theta/2)\) (with \(z\) being the altitude at that point), is at least \(d + r\), where \(d\) is the perpendicular distance from the island’s center to the flight path. (In other words, the entire circle lies within the captured line segment at that point.)

Formally, for a flight starting at \(A=(x_1,y_1)\) with altitude \(z_1\) and ending at \(B=(x_2,y_2)\) with altitude \(z_2\), let the ground projection be the line segment from \(A\) to \(B\) of length \(L\). For any island with center \(C\) and radius \(r\), denote by \(p\) the distance along \(AB\) of the projection of \(C\) onto the line, clamped into the interval \([0,L]\). The flight covers the island if \[ z_1 + \frac{(z_2-z_1)p}{L}\tan\Bigl(\frac{\theta}{2}\Bigr) \ge d + r, \] where \(d\) is the perpendicular distance from \(C\) to \(AB\).

Solve the problem by finding the smallest \(\theta\) (with \(0 < \theta \le \pi\)) for which every island is covered by at least one flight.

inputFormat

The first line contains two integers (n) and (m) ((1 \le n, m \le 10^5)), representing the number of islands and the number of flights respectively.

The next (n) lines each contain three space‐separated real numbers: (x), (y) and (r), where ((x, y)) is the center and (r) is the radius of an island.

The following (m) lines each contain six space‐separated real numbers: (x_1), (y_1), (z_1), (x_2), (y_2), (z_2), describing a flight path from ((x_1, y_1, z_1)) to ((x_2, y_2, z_2)).

outputFormat

Output a single real number: the minimum aperture angle (\theta) in radians that allows every island to be fully covered by at least one flight. Answers within an absolute or relative error of (10^{-6}) will be accepted.

sample

3 2
0 0 1
10 0 1
5 5 1
-1 0 10 11 0 10
0 4 8 10 4 8

0.244978