1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Comparar rectângulos em c#

Discussão em 'Programação' iniciada por Grabitzz, 22 de Setembro de 2006. (Respostas: 12; Visualizações: 913)

  1. Boas,
    eu queria desenvolver um método em c# em k dava o comprimento e a largura de 2 rectângulos, um maior que outro, e me devolvesse quantos rectângulos mais pequeno cabem dentro do rectângulo maior. Alguém me pode ajudar?
     
  2. issues

    issues Power Member

    Olha calculas a area de ambos, depois vês quantas vezes a area do mais pequeno cabe na do maior. facil
     
  3. Nao é assim ta facil! Isso eu tb pensei. E em muitos casos até resulta. Mas nao é regra. Ve este exemplo: o quadrado maior tem 48 de comprimento e 32 de largura, enquanto o pequeno tem 7 de comprimento e 3 de largura. Pelo que dizes têm de caber 73 quadrados pequenos no grande, mas na realidade so consegues meter la 70.
     
  4. SoundSurfer

    SoundSurfer Power Member

    Boas, então o problema não é bem o c#, mas o algoritmo em si...

    O melhor é procurares no google um algoritmo que faça isso mesmo.. se encontrar alguma coisa, coloco aqui.
     
  5. Pois, ja fiz algumas pesquisas no google mas nao encontrei nada, tb nao sei como procurar. Thanks
     
  6. Galbne_PT

    Galbne_PT Power Member

    boas!

    Complicado isso,

    Questao: os rect podem estar misturado uns na horizontal outros na vertical? com espaços no meio?

    Cumps
     
  7. SoundSurfer

    SoundSurfer Power Member

    Algumas ideias:

    Divides os rectângulos pequenos em 2 tipos:

    na "horizontal" ou na "vertical" em relação ao rectângulo original.

    rv = rectangulo pequeno na vertical
    rh = rectangulo pequeno na horizontal

    r*l = lado pequeno
    r*L = lado grande

    R = rectângulo grande.

    ora:

    RL >= (A x rhl + B x rvL)
    Rl >= (A x rhL + B x rvl )

    já é um começo.
     
  8. Warrior

    Warrior Power Member

    Saiu um exercício semelhante a esse nas Olimpiadas Internacionais de Informatica de 1995 (um pouco mais complicado)..
    Por acaso sei isso porque estou a tenta-lo resolver no USACO, assim que chegar à solução posto-a aqui..

    (Dados 4 rectangulos de diferentes medidas, qual a menor área em que é possivel agrupá-los (são permitidas rotações))


    Embora este pareça mais facil.. Acho que podes resolver testando só duas coisas:

    Colocas todos os rectangulos que puderes (enquanto couberem) no lado inferior esquerdo, e vais crescendo para cima e para a direita. Depois rodas-lo, e tentas encaixar no espaço que ficou entre o superior e a parede, e a mesma coisa no lado direito..

    Guardas o resultado de quantos couberem, rodas o rectângulo 90º, e tentas ao contrario.
    Julgo que é suficiente.


    EDIT: lembrei-me agora que não é. Podem existir duas filas de rectangulos no final, ou 3 etc..
    De qualquer das formas o que eu escrevi está tão confuso que ninguem percebeu e não
     
  9. Tenho aqui este pedaço de código so k ainda não está perfeito... Em muitos casos tem um erro de 2 rectangulos

    aqui fica o codigo:

     
  10. Favas

    Favas Power Member

    Problema complicado, deixa-me pensar.

    Ora, tens o rectangulo grande não é, pegas no comprimento do retangulo pequeno e divides o comprimento do rectangulo pequeno pelo comprimento do rectangulo grande, no fim guardas o resto.
    Fazes o mesmo com a altura do pequeno a dividir pela altura do grande e agora somas ao resto obtido anteriormente e guardas.
    Agora, rodas o quadrado pequeno, que é a mesma coisa que trocar o comprimento pela a altura, voltas a fazer as divisões, somar os restos e guardar.

    Fazes uma comparação entre os restos e a posição que tiver menos resto, é a posição ideal para enxer o rectangulo grande até a cima.

    Mas ainda nao acabou.

    Se subtrair-mos o conjunto de rectangulos que enxemos ao rectangulo grande, ficamos com uma area em forma de L (roda o L mentalmente sff).
    Podes dividir esse L em 2 rectangulos e voltar a encher de rectangulos pequenos com o mesmo algoritmo.

    Não sei é o algoritmo ideal, mas foi o melhor que consegui pensar (em 5 mins).

    Cumps e boa sorte.

    EDIT: depois de dar uma vista de olhos pelo teu codigo, é +- isto que tás a tentar, ou não?
     
    Última edição: 25 de Setembro de 2006
  11. O k estou a fazer é rodar o rectangulo pequeno para caber no L, nao sei se em vez de rodar o rectangulo, rodar o L vai dar mais resultado... Tenho de experimentar.
     
  12. Warrior

    Warrior Power Member

    Isso não vai dar a solução ideal, isso foi o que eu sugeri em cima (embora de modo muito mais confuso) mas lembrei-me de um promenor:

    -----------------
    | | | | |
    ---------- | | |
    | | | | |
    -----------------
    | | | | |
    ---------- | | |
    | | | | |
    -----------------

    4 filas de dois rectangulos horizontais e 2 verticais num total de 12 rectângulos

    Num input em que esta seja a solução ideal (e é, pois não existe nenhum espaço livre dentro do rectângulo maior), o resultado vai ser incorrecto, uma vez que pode ser necessário rodar mais do que uma fila de rectângulos para ganhar algum espaço..


    EDIT: O submit retirou-me os espaços extra e o desenho ficou estragado..
     
  13. Cesaria

    Cesaria Power Member

    Ora viva, já pensaste em utilizar heuristicas? Acho que poderá ser uma boa solução pelo aquilo que percebi do teu prob... O único problema das heuristicas consiste na possibilidade de não encontrares sempre a mesma solução, conforme a dificuldade do problema poderás só obter boas soluções mt próximas da solução optima e noutros casos ate mesmo a sua solução optima. Se pretenderes experimentar diz qq coisa, um bom método que podes começar a usar, ("se quiseres") é o método Greedy em que dás um determinado tempo de execução e em cada iteração fazes uma construção aleatoria dos rectangulos no final só vais guardando a solução que der maior número de quadraditos...

    Fica aqui a minha sugestão, li isto bem rápido por isso posso tar mm mta enganado em relação ao prob, mas tb já são quase 4 da matina,ehehehe...

    Cumprimentos
     

Partilhar esta Página