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.|

CHUVA08 - Chuva

A robótica causou uma grande revolução nos processos industriais no mundo todo; atualmente, vários tipos de robôs são usados na fabricação de carros, equipamentos eletrônicos e até mesmo utensílios domésticos.

Uma fábrica possui um robô de manutenção, que constantemente precisa ser deslocado entre setores diferentes para executar vários serviços. A movimentação do robô é feita por controle remoto: ele pode andar qualquer distância, mas apenas nas quatro direções cardeais (norte, sul, leste e oeste).

Robôs são feitos de metal, e por isso é ideal que eles evitem contato direto com a água. Assim, em dias chuvosos, é ideal que a trajetória do robô passe por dentro de galpões, debaixo de marquises e toldos, etc. para evitar sua exposição à chuva.

A sua tarefa é escrever um programa que, dadas as informações sobre as áreas cobertas e ponto inicial e final do robô, determine uma trajetória para o robô que minimize a porção do trajeto feita sob chuva.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém quatro inteiros Xi, Yi, Xf e Yf (0 ≤ Xi, Yi, Xf, Yf ≤ 106), indicando, respectivamente, a posição atual e a posição final do robô — o robô começa na posição (Xi, Yi) e deve terminar na posição (Xf , Yf).

A linha seguinte da entrada contém um único inteiro N (0 ≤ N ≤ 1000), indicando o número de áreas cobertas na fábrica. Cada uma das N linhas seguintes contém quatro inteiros X1, Y1, X2 e Y2 (0 ≤ X1 < X2 ≤ 106, 0 ≤ Y1 < Y2 ≤ 106), indicando uma região coberta.

Uma região coberta é um retângulo de lados paralelos aos eixos tal que (X1, Y1) e (X2, Y2) são vértices opostos do retângulo. Duas áreas cobertas podem ter regiões comuns. O robô pode entrar e sair de uma área coberta por qualquer ponto de seu perímetro, e pode trafegar livremente dentro da área coberta.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um número inteiro indicando a menor distância que o robô precisa percorrer sob chuva.

Exemplos

Entrada:
0 0 4 3
0

Saída:
7
Entrada:
2 5 5 0
1
0 0 1 5

Saída:
5
Entrada:
4 5 5 0
2
0 0 1 5
0 0 3 2

Saída:
5

Adicionado por:Wanderley Guimarăes
Data:2012-12-14
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2008 - fase 2 nível 2

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