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.
Quando Compadre Roberto recebeu o fax, achava que esses terrenos tinham 2 * 4 + 3 * 3 + 4 * 1 = 21 Km2no total. Agora sabe que são 18 Km2...
Ele gostaria de saber quantos Km2os 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.
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.
Pergunta
pokiha
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.
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.
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
Link da questão direto do SPOJ
Desde já agradeço muitíssimo a quem puder ajudar
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.