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

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

Robo marciano

Uma empresa de turismo aeroespacial está se preparando para a exploração comercial de Marte. Ela implantou uma base de operações no planeta, onde conduz experimentos que visam garantir a segurança de futuros turistas.

A base em Marte é composta por um conjunto de áreas retangulares cobertas por um teto protetor contra a radiação solar. As áreas retangulares têm lados paralelos aos eixos Norte-Sul e Leste-Oeste. Vários robôs, controlados por comandos enviados desde o Centro de Operações da empresa, na Terra, deslocam-se constantemente pela base para acessar materiais e equipamentos.

Os robôs podem deslocar-se apenas nas quatro direções cardeais (norte, sul, leste e oeste), mas podem transitar tanto em áreas cobertas como não cobertas. Em particular, um robô pode entrar e sair de uma área coberta por qualquer ponto da borda dessa área. Para preservar a vida útil dos robôs, é importante que eles se mantenham o máximo possível protegidos da intensa radiação solar, ou seja, que eles transitem preferencialmente nas áreas cobertas da base.

Dadas as descrições das áreas cobertas, a posição atual de um robô e a posição para a qual este robô deve se deslocar, sua tarefa é determinar a menor distância que o robô deve percorrer fora das áreas cobertas para chegar à posição de destino.

Entrada

A primeira linha da entrada contém quatro inteiros Xi, Yi, Xf e Yf indicando, respectivamente, a posição inicial do robô, (Xi, Yi) e a posição final do robô, (Xf,Yf).

A segunda linha contém um único inteiro N, indicando o número de áreas cobertas. Cada uma das N linhas seguintes contém quatro inteiros X1, Y1, X2 e Y2 indicando uma região retangular coberta, tal que (X1, Y1) e (X2,Y2) são vértices opostos do retângulo de lados paralelos aos eixos. Duas áreas cobertas podem ter regiões comuns.

Saída

Seu programa deve produzir uma única linha, contendo uma única linha, com um único número inteiro, a menor distância que o robô deve percorrer em áreas não cobertas para ir da posição inicial à posição final do robô.

Restrições

  • 0 ≤ N ≤ 1000
  • 0 ≤ Xi, Yi, Xf , Yf ≤ 106
  • 0 ≤ X1 ≤ X2 ≤ 106 e 0 ≤ Y1 ≤ Y2 ≤ 106

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 30 pontos, X1,Y1,X2,Y2,Xi,Xf,Yi,Yf ≤ 10 e N ≤ 5.
  • Para um conjunto de casos de testes valendo outros 50 pontos, X1,Y1,X2,Y2,Xi,Xf,Yi,Yf ≤ 1000 e N ≤ 100.

Exemplos

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

 

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
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação