13696번 - Regata de Cientistas 다국어

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 (x₁, y₁) e (x₂, y₂). 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.

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 x_i = y_i = x_f = y_f = n = 0.

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