XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: chuva.x, onde x deve ser c, cpp, java, js ou py

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.

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 30 pontos, X1, Y1, X2, Y2, Xi, Xf, Yi, Yf ≤ 10 e N ≤ 5.
  • Em um conjunto de casos de teste que totaliza 55 pontos, X1, Y1, X2, Y2, Xi, Xf, Yi, Yf ≤ 1000 e N ≤ 100.

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
			
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação