Jump to content
Fórum Script Brasil
  • 0

Problema Spoj Ajuda


pokiha
 Share

Question

Olá, boa noite.

Sou iniciante e estudante de programação. Estou com muita dificuldade pra manipulação de matriz e travei em uma questão do Spoj.

Vou postar aqui a questão e se alguém puder me ajudar, dando um norte de por onde eu deveria começar, agradeço MUITO. 
 

FAZENDMG - Fazenda

 

Compadre Roberto teve uma agradável surpresa: recebeu um telefonema de sua irmã dizendo que eles eram os únicos herdeiros das terras dos seus tios. Logo em seguida recebeu um fax com a descrição dos terrenos. Todos eram retangulares, e pela largura e comprimento de cada um concluiu que herdou uma grande área de terra no triângulo mineiro! Não tardou e Compadre Roberto já estava lá para tomar posse dos terrenos.

Chegando lá, uma surpresa nada agradável... os terrenos eram sobrepostos!! Ninguém conseguiu explicar como isso aconteceu, mas boa parte das terras dos seus tios não pertenciam a apenas um, mas a dois ou mais! Isso nunca foi problema para eles, que cuidavam de tudo como uma grande família, sem se preocupar exatamente que pedaço era de quem. Tampouco é problema para Compadre Roberto e sua irmã, que agora são os únicos donos. Mas é frustrante descobrir que o terreno não era tudo o que pensava...

A figura abaixo mostra um exemplo com 3 terrenos. Os terrenos são descritos com quatro números inteiros X, Y, L, C, indicando que o canto sudoeste do terreno (na figura, o canto inferior esquerdo) está na coordenada (X,Y) e ele tem largura L e comprimento C (todos os valores dados em Km). A descrição dos 3 terrenos mostrados é: Terreno A: 1 2 2 4; Terreno B: 2 0 3 3; Terreno C: 0 4 4 1. A figura da esquerda mostra os terrenos, e a da direita o terreno total resultado da sobreposição.

wanderley:fazenda.png

Quando Compadre Roberto recebeu o fax, achava que esses terrenos tinham 2 * 4 + 3 * 3 + 4 * 1 = 21 Km2 no total. Agora sabe que são 18 Km2...

Ele gostaria de saber quantos Km2 os terrenos realmente contêm. E com as muitas sobreposições precisa da sua ajuda. Além disso precisa cercar o terreno, então gostaria de saber também quantos Km de cerca são necessários. No exemplo acima a cerca tem 24 Km de comprimento.

Observações

A junção dos terrenos nem sempre forma uma região contígua e sem “buracos”. Casos como os mostrados na figura abaixo podem acontecer. Então nem sempre será possível cercar o terreno herdado com uma única cerca contígua, pode ser necessário usar mais de uma.

wanderley:fazenda2.png

Entrada

Há vários casos de teste.

A primeira linha de um caso de teste contém um número inteiro N que é o número de terrenos herdados (N ≤ 20). As N linhas seguintes contém cada uma a descrição de um terreno no formato X Y L C conforme descrito no enunciado ( 0 ≤ X, Y ≤ 1000, e 1 ≤ L, C ≤ 500).

A entrada termina quando N = 0

Saída

Para cada caso de teste da entrada seu programa deve produzir uma linha na saída contendo dois valores A e P, que são a área (em Km2) e o perímetro (em Km) total da união dos terrenos descritos no caso de teste.

Exemplos

Entrada:
3
1 2 2 4
2 0 3 3
0 4 4 1
5
1 2 1 1
1 2 5 1
2 5 4 2
4 0 1 6
1 0 2 4
4
0 0 1 4
0 3 4 1
3 0 1 4
1 0 2 1
0

Saída:
18 24
23 36
12 24

 

Link da questão direto do SPOJ

 

 

Desde já agradeço muitíssimo a quem puder ajudar

Link to comment
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Forum Statistics

    • Total Topics
      149.6k
    • Total Posts
      646.2k
×
×
  • Create New...