Olá meus amigos nerds, hoje vamos ajudar nossos queridos amigos pescadores a saber qual é a área do mar que suas redes são capazes de cobrir. Já que é isso que o problema 11009. O mar não está para peixe nos pede.
Mais especificamente dadas as dimensões de cada rede e o local onde cada uma delas é jogada desejamos determinar a área do mar que essas redes cobrem.
Solução
Esse é um problema que considero interessante, já que o caso geral dele, que é calcular a área da sobreposição de figuras geométricas arbitrárias, é um problema bastante complexo. Entretanto o problema 11009 é fácil devido a duas restrições:
- As redes são retangulares
- As dimensões das redes são números inteiros
Assim, podemos tratar o mar como um grid, onde cada célula tem área 1. Após isso basta marcar as posições ocupadas pelas redes e depois contar quantos quadradinho de área 1 temos no grid. Essa abordagem tem custo quadrático, mas o tamanho da entrada é pequeno (100) isso é suficiente para que o problema seja aceito.
Nenhum comentário:
Postar um comentário