Pandemic Restrictions
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: geometry, ternary search

After a long time living abroad, you have decided to move back to Italy and have to find a place to live, but things are not so easy due to the ongoing global pandemic.

Your three friends Fabio, Flavio and Francesco live at the points with coordinates $$$(x_1, y_1), (x_2, y_2)$$$ and $$$(x_3, y_3)$$$, respectively. Due to the mobility restrictions in response to the pandemic, meetings are limited to $$$3$$$ persons, so you will only be able to meet $$$2$$$ of your friends at a time. Moreover, in order to contain the spread of the infection, the authorities have imposed the following additional measure: for each meeting, the sum of the lengths travelled by each of the attendees from their residence place to the place of the meeting must not exceed $$$r$$$.

What is the minimum value of $$$r$$$ (which can be any nonnegative real number) for which there exists a place of residence that allows you to hold the three possible meetings involving you and two of your friends? Note that the chosen place of residence need not have integer coordinates.

Input format:
The first line contains the two integers $$$x_1, y_1$$$ ($$$-10^4 \le x_1, y_1 \le 10^4$$$) — the coordinates of the house of your friend Fabio.

The second line contains the two integers $$$x_2, y_2$$$ ($$$-10^4 \le x_2, y_2 \le 10^4$$$) — the coordinates of the house of your friend Flavio.

The third line contains the two integers $$$x_3, y_3$$$ ($$$-10^4 \le x_3, y_3 \le 10^4$$$) — the coordinates of the house of your friend Francesco.

It is guaranteed that your three friends live in different places (i.e., the three points $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$(x_3, y_3)$$$ are guaranteed to be distinct).

Output format:
Print the minimum value of $$$r$$$ which allows you to find a residence place satisfying the above conditions. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample, Fabio, Flavio and Francesco live at the points with coordinates $$$(0,0)$$$, $$$(5,0)$$$ and $$$(3,3)$$$ respectively. The optimal place of residence, represented by a green house in the picture below, is at the point with coordinates $$$(2.3842..., 0.4151...)$$$.

In the second sample, any point on the segment $$$\{(x,0):\ -1 \leq x \leq 1 \}$$$ is an optimal place of residence.

Example input:
0 0
5 0
3 3

Example output:
5.0686143166

Example input:
-1 0
0 0
1 0

Example output:
2.0000000000

Editorial:
Let us start with some definitions that will make the presentation clearer. Given three points $$$X, Y$$$ and $$$Z$$$ in the plane, let $$$f(X, \, Y, \, Z)$$$ be the minimum of $$$\overline{XP}+\overline{YP}+\overline{ZP}$$$ over all points $$$P$$$. It is well known that this minimum actually exists and is achieved at a unique point called the Fermat point of the triangle $$$XYZ$$$.
For fixed $$$X$$$ and $$$Y$$$, let $$$f_{XY}(Z) := f(X, \, Y, \, Z)$$$ and define $$$$$$g(W) := \max(f_{AB}(W), \, f_{AC}(W), \, f_{BC}(W)),$$$$$$ where $$$A, B$$$ and $$$C$$$ are the positions of the three friends.
For a given parameter $$$r$$$, the condition that $$$Z$$$ is a valid residence point is equivalent to $$$g(Z) \leq r$$$. Thus, no valid residence point exists if and only if $$$\min g > r$$$, and therefore the minimum value of $$$r$$$ that works is equal to the minimum of $$$g$$$ over all points of the plane.
We claim that $$$g$$$ is convex, hence this minimum exists and we can find it efficiently. This relies on the following two observations:
• The pointwise maximum of a finite set of convex functions is convex.
• The function $$$f_{XY}$$$ is convex.
The first observation is a standard fact. For the second observation, let $$$X, \, Y$$$ be two points, $$$0 \leq t \leq 1$$$, and let $$$P, \, Q$$$ be the respective Fermat points of the triangles $$$ABX$$$ and $$$ABY$$$. Then, denoting $$$Z = tX + (1-t)Y$$$ and $$$R = tP + (1-t)Q$$$, we have that $$$$$$\overline{AR} = |A - tP - (1-t)Q| \leq t \overline{AP} + (1-t)\overline{AQ},$$$$$$ $$$$$$\overline{BR} = |B - tP - (1-t)Q| \leq t \overline{BP} + (1-t)\overline{BQ},$$$$$$ and $$$$$$\overline{ZR} = |t(X-P) + (1-t)(Y-Q)| \leq t \overline{XP} + (1-t)\overline{YQ},$$$$$$ so adding up the three inequalities we get that $$$$$$f_{AB}(Z) \leq \overline{AR}+\overline{BR}+\overline{ZR} \leq t f_{AB}(X) + (1-t) f_{AB}(Y).$$$$$$
In view of these facts, if we know how to compute $$$f(X, \, Y, \, Z)$$$ efficiently we can solve the problem with a double ternary search on $$$g$$$. There are ways to achieve this in $$$\mathcal O(1)$$$ time by distinguishing two cases:
• If one of the angles of triangle $$$XYZ$$$ is greater than $$$2 \pi / 3$$$, then the corresponding vertex is the Fermat point.
• Otherwise the Fermat point can be computed using the construction of the Napoleon triangle, or the sum of its distances can be computed more straightforwardly using the following formula: $$$$$$f(X, \, Y, \, Z) = \sqrt{\frac{a^2+b^2+c^2+4\sqrt{3}S}{2}}.$$$$$$ (Here $$$a, \, b, \, c$$$ are the sidelengths and $$$S$$$ is the area of the triangle.)