Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

REGATA - 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 (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 xi, yi, xf, yf e n, representando respectivamente as coordenadas do ponto de iníıcio (xi, yi), as coordenadas do ponto de chegada (xf, yf) 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 x1, y1, x2 e y2 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

Adicionado por:Wanderley Guimarăes
Data:2009-06-23
Tempo limite:1s-1.442s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2005

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.