|
|
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.
SPOJ Problem Set (regionais)
4520. Regata de Cientistas
Problema: REGATA
|
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-4s |
| Tamanho do fonte: | 50000B |
| Linguagem permitida: | Todas exceto: AWK CLOJ ERL F# GO JS PERL 6 SCALA SED TCL |
| Origem: | Primeira fase da Maratona de Programação - 2005 |
|
|
|
|