시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

입력

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.

출력

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

예제 입력 1

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

예제 출력 1

10.20
10.00

힌트