Navegacao

Andre94
(usa Fedora)

Enviado em 19/09/2013 - 15:45h

Boa tarde, tenho como tarefa fazer um algoritmo para o problema abaixo. Acontece que nao sei como fazer mesmo... Preciso urgente de ajuda... Obrigado...


Navegação Fluvial

Suponha que a largura em metros de um rio navegável é dada por um valor inteiro L. Os técnicos em navegação fizeram um perfil do leito do rio medindo sua profundidade a cada metro, a partir da margem esquerda. Assim, por exemplo, no i-ésimo metro, a profundidade do rio é dada por um valor inteiro não negativo P(i), sendo que nas margens esquerda e direita as profundidades são P(0) e P(L), respectivamente, ambas com valor nulo (ou seja, P(0) = P(L) = 0).

As seguintes hipóteses são consideradas neste exercício:

O perfil do leito do rio não muda ao longo do trecho navegável, e
entre duas medidas consecutivas de profundidade P(i) e P(i+1), pode-se considerar que a profundidade varia linearmente entre estes dois valores. Assim, se K é um valor real no intervalo [0,1], o valor da profundidade no metro (i+K) considerado a partir da margem esquerda, será dado por P(i) + K*(P(i+1)-P(i)).
No seu dia a dia, os técnicos se deparam com o seguinte problema. Um navio de largura W e calado (profundidade máxima a partir da superfície) C pretende navegar pelo rio. Os técnicos precisam determinar se existe uma distância segura de navegação, a contar da margem esquerda, que permite que o navio navegue pelo rio. A resposta dada pelo técnicos ao capitão do navio é um valor real (double) X tal que:

X é igual a -1.000000 se o navio não pode navegar pelo rio (nota: supõe-se aqui que o calado do navio é o mesmo ao longo de toda a sua largura), e
X é o menor valor positivo (distância da margem esquerda) que o navio pode navegar com segurança. Isso ocorre se, no trecho que vai de [X, X+W] a profundidade do rio é sempre maior ou igual a C + 0.1.




O objetivo desta tarefa é ajudar os técnicos de navegação fazendo um programa que gera a resposta a ser dada ao capitão do navio. Para tanto, considere as especificações de entrada e saída dadas a seguir.

Entrada: duas linhas com valores inteiros separados por um espaço em branco entre eles. Na primeira linha são dados L, no intervalo (fechado) [2, 50], W e C, no intervalo (fechado) [1, 25]. Na segunda linha, são dados L-1 valores correspondentes às profundidades a 1, 2, ..., L-1 metros da margem esquerda (lembre-se que as profundidades nas duas margens são nulas).

Saída: um valor double, impresso com seis casas decimais, correspondendo à posição X mais à esquerda na qual o navio pode navegar ou ao valor -1.000000, quando o calado do navio não permite que ele navegue pelo rio.

Observações
Você deve quebrar a linha após imprimir o resultado.
Exemplos de execução

Exemplo 1:
2 1 1
3
0.366667

Exemplo 2:
2 1 1
2
-1.000000

Exemplo 3:
6 1 3
3 2 4 3 5
2.550000

Exemplo 4:
6 2 3
3 2 4 2 5
-1.000000

Exemplo 5:
12 2 17
41 7 32 24 2 12 15 39 29 27 38
7.087500

Grato, André