FRAKTAL - konkurs programistyczny

Radio

Miejscowa rozgłośnia radiowa wychodząc naprzeciw oczekiwaniom mieszkańców, postanowiła dotrzeć z informacjami do każdego gospodarstwa w okolicy. Rozgłośnia ta posiada dwa maszty nadawcze ulokowane w różnych miejscach. Trzeba je nastawić, aby wysyłały fale radiowe na takie odległości, które swoim zasięgiem obejmą wszystkie gospodarstwa w okolicy. Po szerokich konsultacjach społecznych postanowiono, że przy regulacji masztów musi być uwzględniony warunek zminimalizowania obszaru zasięgu fal radiowych, bo podobno fale te źle wpływają na samopoczucie zwierząt zamieszkujących pobliskie lasy. Trzeba więc tak dobrać długość promieni fal radiowych obu masztów, aby łączny obszar ich zasięgu był możliwie najmniejszy. Znając współrzędne masztów i współrzędne wszystkich gospodarstw napisz program, który wyznaczy sumę długości promieni zasięgu fal obu masztów, uwzględniając czynnik zminimalizowania obszaru zasięgu fal radiowych. Należy założyć, że czasami wystarczy uruchomić tylko jeden maszt, którego obszar zasięgu fal będzie wystarczający do spełnienia warunków podanych wyżej. .

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. W pierwszym wierszu każdego zestawu znajduje się pięć liczb całkowitych n, x₁, y₁, x₂, y₂ (2 ≤ n ≤ 10⁴, -10³ x₁, y₁, x₂, y₂ ≤ 10³), gdzie n to liczba gospodarstw, a x₁, y₁, x₂, y₂, to współrzędne całkowite dwóch masztów. Dalej w n wierszach podane są współrzędne gospodarstw, w każdym wierszu dwie liczby całkowite x, y (-10³ ≤ x, y ≤ 10³).

Wyjście
Na wyjściu należy wypisać sumę długości promieni fal radiowych obu masztów (z dokładnością do dwóch cyfr po przecinku) obejmujących swoim zasięgiem wszystkie gospodarstwa i jednocześnie spełniających warunek zminimalizowania obszaru zasięgu fal radiowych.

Przykład

Wejście
3
3 2 2 5 3
3 4
5 1
2 1
3 0 3 3 -1
1 -1
0 1
-1 2
3 1 1 2 2
0 0
3 3
4 4

Wyjście
3.24
4.00
2.83