SPOJ Brasil

Todos os anos, desde 1996, cientistas da computação do mundo todo se encontram para a famosa Regata dos Cientistas. A competição consiste em uma corrida de barcos com obstáculos pelo oceano, onde o objetivo de cada equipe é, partindo de um ponto em comum, alcançar o ponto de chegada sem que nenhum obstáculo seja tocado ou transpassado. Uma equipe que toca ou transpassa um obstáculo é automaticamente desclassificada. A equipe vencedora é aquela que primeiro atinge o ponto de chegada (o ponto de chegada é distinto do ponto de início).

Você foi contratado pela equipe brasileira para desenvolver um programa que calcule o comprimento da menor rota válida possível do ponto de partida ao ponto de chegada.

O oceano é considerado um plano infinito, onde cada obstáculo é localizado em uma posição fixa e representado por um segmento de reta descrito por seus dois extremos (x1, y1) e (x2, y2). Os barcos são adimensionais (representados como um ponto no plano) e os obstáculos possuem espessura desprezível.

Os obstáculos são dispostos de tal forma que os mesmos não se interceptam. De forma similar, os pontos de início e de chegada da competição não são interceptados por nenhum obstáculo.

Entrada

A entrada é composta por vários casos de teste. A primeira linha de um caso de teste contém cinco números inteiros x_i, y_i, x_f, y_f e n, representando respectivamente as coordenadas do ponto de iníıcio (x_i, y_i), as coordenadas do ponto de chegada (x_f, y_f) e a quantidade de obstáculos (n <= 150). Cada uma das n linhas seguintes de um caso de teste contém quatro números inteiros x₁, y₁, x₂ e y₂ que descrevem as coordenadas dos dois extremos de um obstáculo. Considere que as coordenadas x e y de qualquer ponto satisfazem −5000 <= x, y <= 5000. O final da entrada é representado por uma linha contendo xi = yi = xf = yf = n = 0.

Saída

Para cada caso de teste, imprima uma linha contendo o comprimento da menor rota válida possível, arredondado para duas casas decimais.

Exemplo de entrada

0 0 10 0 1
5 -1 5 1
0 0 10 0 1
5 0 5 1
0 0 0 0 0

Saída para o exemplo de entrada

10.20
10.00