Regional Integration
Description
The distant and modern city of Extremopolis is located right on the triple border between the nations of Circland, Squareland, and Triangland.
For this reason, the city has many buildings. These buildings can only be of 3 possible types:
- The base of the building is circle-shaped.
- The base of the building is square-shaped (not necessarily aligned with the axes). A square is a quadrilateral with all $4$ sides equal and all $4$ angles right angles.
- The base of the building is triangle-shaped (not necessarily aligned with the axes).
You have a detailed map of the city, which shows the circles, squares, and triangles representing the bases of the different buildings. Two of these figures never intersect or touch each other, not even at a vertex, as they are different buildings.
The Institute of Coordination and Planning of Circland (ICPC) plans to open two new business offices: one should be located in a building with a triangular base, and the other in a building with a square base. With this, the institute aims to improve its commercial relations with neighboring countries.
Another extreme characteristic of Extremopolis is that it is located on the equator, has a very dry climate, and practically no cloudy days. Therefore, the level of ultraviolet radiation from the sun that its inhabitants experience is extremely high. Taking this into account, the ICPC wants to select the two buildings where it will open the new offices in such a way that walking from one to the other requires walking in the sun as little as possible.
Extremopolis has no streets or obstacles that obstruct the way, so it is possible to walk freely through any point in the city. All buildings are designed with a spacious and obstacle-free ground floor, so it is even possible to walk freely through the base of the buildings (i.e., the entire interior of the circle, square, or triangle), and these walking distances inside the buildings do not count towards the total distance walked under the sun.
Your task is to compute the minimum distance that needs to be walked under the sun to travel between both offices, if they are opened in the ideal buildings to minimize that distance.
The first line contains three integers $C$, $Q$, $T$: the number of buildings with circular base ($0 \leq C$), square base ($1 \leq Q \leq 10^5$), and triangular base ($1 \leq T \leq 10^5$) respectively.
It is also known that $(T+C) (Q+C)\leq 10^6$.
Each of the following $C$ lines describes a building with a circular base using $3$ integers $x,y,r$. The corresponding circle has its center at $(x,y)$ and radius $r$.
Each of the following $Q$ lines describes a building with a square base using $4$ integers $x_1, y_1, x_2, y_2$. The corresponding square has a pair of opposite vertices at $(x_1,y_1)$ and $(x_2,y_2)$. It is guaranteed that these are two distinct points in the plane, i.e., $(x_1,y_1) \neq (x_2,y_2)$.
Each of the following $T$ lines describes a building with a triangular base using $6$ integers $x_1, y_1, x_2, y_2, x_3, y_3$. The corresponding triangle has its three vertices at the points $(x_1,y_1)$, $(x_2,y_2)$, and $(x_3,y_3)$. It is guaranteed that these are three distinct points in the plane, and they are not collinear (the triangle is not degenerate).
The radii $r$ and all coordinates $x,y$ are integers between $1$ and $10^9$ inclusive.
It is guaranteed that there will be no two buildings whose bases intersect, not even at a point on their boundary.
A single line with a single number: the minimum distance that needs to be walked under the sun while fulfilling the requirements.
This answer will be accepted if it has a relative or absolute error less than or equal to $10^{-6}$.
Formally, let $a$ be your answer and $b$ be the jury's answer. Then, your answer will be accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.
Input
The first line contains three integers $C$, $Q$, $T$: the number of buildings with circular base ($0 \leq C$), square base ($1 \leq Q \leq 10^5$), and triangular base ($1 \leq T \leq 10^5$) respectively.
It is also known that $(T+C) (Q+C)\leq 10^6$.
Each of the following $C$ lines describes a building with a circular base using $3$ integers $x,y,r$. The corresponding circle has its center at $(x,y)$ and radius $r$.
Each of the following $Q$ lines describes a building with a square base using $4$ integers $x_1, y_1, x_2, y_2$. The corresponding square has a pair of opposite vertices at $(x_1,y_1)$ and $(x_2,y_2)$. It is guaranteed that these are two distinct points in the plane, i.e., $(x_1,y_1) \neq (x_2,y_2)$.
Each of the following $T$ lines describes a building with a triangular base using $6$ integers $x_1, y_1, x_2, y_2, x_3, y_3$. The corresponding triangle has its three vertices at the points $(x_1,y_1)$, $(x_2,y_2)$, and $(x_3,y_3)$. It is guaranteed that these are three distinct points in the plane, and they are not collinear (the triangle is not degenerate).
The radii $r$ and all coordinates $x,y$ are integers between $1$ and $10^9$ inclusive.
It is guaranteed that there will be no two buildings whose bases intersect, not even at a point on their boundary.
Output
A single line with a single number: the minimum distance that needs to be walked under the sun while fulfilling the requirements.
This answer will be accepted if it has a relative or absolute error less than or equal to $10^{-6}$.
Formally, let $a$ be your answer and $b$ be the jury's answer. Then, your answer will be accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.
2 1 1
10 1 5
20 1 4
1 1 4 4
24 5 28 50 45 4
0 1 1
1 1 4 4
5 1 5 10 10 1
0 2 2
1 1 10 2
3 12 2 20
50 10 50 100 100 10
450 410 450 4100 4100 410
3.656854249
1.0
40.792156108
Note
In the first two examples, there is only one building with a square base and one building with a triangular base, so those must be chosen to open the offices.
In the first example, to walk the shortest distance under the sun, it is convenient to pass through the buildings with circular bases.
Note that in the third example, the squares are not aligned with the axes.