AlgoLiga 2018

Długość trasy

Organizatorzy slalomu kajakowego poprosili Cię o wyznaczenie długości trasy jaką przygotowali. Trasa rozpoczyna się w punkcie startu, biegnie pomiędzy tyczkami i kończy się na odcinku ostatniej bramki. Znając koordynaty punktu startu, liczbę bramek na rzece oraz ich koordynaty, nie powinno być to trudne.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ n ≤ 1000) oznaczającą liczbę zestawów danych. Pierwszy wiersz każdego zestawu zawiera trzy liczby x, y, n (1 ≤ x, y ≤ 10⁵, 1 ≤ n ≤ 1000), gdzie x i y oznaczają współrzędne kartezjańskie punktu startu, a liczba n to liczba bramek na trasie. W kolejnych n wierszach podane są po trzy liczby całkowite y, x₁ < x₂ (0 ≤ y, x₁, x₂ ≤ 10⁵), oznaczające współrzędne kartezjańskie tyczek kolejnych bramek. Każda bramka opisana jest za pomocą współrzędnych (x₁, y) i (x₂, y) i jest równoległa do osi OX. Wszystkie trójki liczb podane na wejściu posortowane są malejąco według współrzędnej y, a ostatnia bramka jest linią mety.
Pliki wejściowe nie przekraczają 3MB.

Wyjście
Dla każdego zestawu należy wypisać długość najkrótszej drogi od startu do mety z dokładnością do co najmniej dwóch cyfr po przecinku.

Przykład

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

Wyjście
3.41
3.00