Encontrar maior retãngulo em um grafico

Basicamente recebemos um terreno de no máximo 100000x100000 e recebemos no máximo 1000 posições (x,y), e a saída deverá ser o maior retângulo livre destes pontos (x,y).

Bem, as soluções que cheguei funcionam, porém todas baseiam-se em armazenar, em uma matriz, todas as posições possíveis e então marcar (um boolean) posições onde tem os pontos recebidos, e para cada posição da matriz eu tento formar retângulos.

Basicamente o que faço é um brute force, e esta ocupando muita memoria em casos maiores.

Alguém tem alguma ideia de resolução sem precisar armazenar todos os pontos possíveis? usando somente as posições recebidas talvez…

Não preciso de soluções apenas ideias.…

1 Resposta

diego12 18 de set. de 2017

Talvez consiga otimizar, exemplo:

No primeiro quadro tem apenas um retângulo.

No segundo, ao colocar um ponto, divide o retângulo em 8 partes.

No terceiro, ao colocar um ponto, divide os retângulos formando 23 retângulos.

No quarto, otimizei, formando um terreno “virtual” de 5x5, cada retângulo tem um peso / área diferentes, portanto poderia usar a mesma solução que vc usou.

A estrutura ficaria:

class Retângulo {
  Point posicaoVirtual; // depende de como vc vai fazer, pois talvez não precise armazenar a posição virtual
  Point posicaoReal;
  public int área();
  boolean éMarca();
}

Também não precisa de uma matriz, pode usar duas listas de retângulos e uma outra de marcas, usar loops para efetuar as buscas e efetuar as operações.

1 Resposta

Topicos relacionados