Comparar rectângulos em c#

G

Grabitzz

Membro
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?
 
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.
 
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.
 
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.
 
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
 
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:

int CompRectPeq //Comprimento do rectangulo pequeno
int LargRecPeq //Largura do rectangulo pequeno
int CompRectGrande //Comprimento do rectangulo grande
int LargRectGrande //Largura do rectangulo grande
int contPlanox = 0; //contador de rectangulos
int contPlanoy = 0;
int contMedx = 0; //contador de medidas dos rectangulos
int contMedy = 0;
int q = 0;
int r = 0;
//Calcula x
while( contMedx + CompRectPeq <= CompRectGrande)
{
contPlanox++;
contMedx = contMedx + CompRectPeq;
}
// calcula y
while( contMedy + LargRecPeq <= LargRectGrande)
{
contPlanoy++;
contMedy = contMedy + LargRecPeq;
}
if(LargRectGrande - contMedy >= CompRectPeq)
q = CompRectGrande / LargRecPeq;
CompRectPeq = LarguraFormato;
LargRecPeq = AlturaFormato;
CompRectGrande = LarguraPapel;
LargRectGrande = AlturaPapel;

int aux = contPlanox * contPlanoy + q;
contPlanox = 0;
contPlanoy = 0;
contMedx = 0;
contMedy = 0;
while( contMedx + CompRectPeq <= CompRectGrande)
{
contPlanox++;
contMedx = contMedx + CompRectPeq;
}
// calcula y
while( contMedy + LargRecPeq <= LargRectGrande)
{
contPlanoy++;
contMedy = contMedy + LargRecPeq;
}
if(LargRectGrande - contMedy >= CompRectPeq)
r = CompRectGrande / LargRecPeq;
int aux1 = contPlanox * contPlanoy + r;
if (aux > aux1)
return aux;
else
return aux1;
}
Clicar para expandir...
 
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:
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.
 
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..
 
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
 
Inicie sessão ou registe-se para poder participar.
Back
Topo