[Algorytmy] Program rozmieszczania prostokątów w arkuszu

[damkur88]

Pisze program dla robota którego zadaniem jest:

Po podaniu wymiaru arkusza tj. wysokości i szerokości, podajemy ilość prostokątów które mają zostać umieszczone w arkuszu, następnie kolejno podajemy długość i szerokość wszystkich prostokątów. Program wpisuje sobie dane prostokątów do tablicy szerokości i długości.
Następnie program sobie oblicza pola prostokątów i sortuje tablice danych z szerokością i długością prostokątów wg pól prostokątów od największych do najmniejszych.

Do tego miejsca mam napisany program, dalej chciałbym, aby program sprawdzał czy dany prostokąt mieści się w arkuszu, jeśli tak zostanie wyrysowany na arkuszu pisakiem przez robota, jeśli nie sprawdza kolejny prostokąt czy się mieści itd. Powinien to robić w sposób optymalny.

Czy wie ktoś jak to zrobić? nie wiem jak program powinien sobie wyznaczać punkty i je pamiętać aby kolejne prostokąty były umieszczane na prostokątach narysowanych wcześniej.

Proszę o pomoc potrzebne mi to do pracy inż. z góry dziękuję.

[lukasz93a]

Mam pewien pomysł, ale wątpię żeby rozwiązanie było optymalne.

Załóżmy, że Twój arkusz ma wymiary \(\displaystyle{ x,y}\), a prostokąty \(\displaystyle{ a_n, b_n}\).
Sprawdzasz pierwszy prostokąt czy się mieści, jeśli tak to rysujesz go (zakładam od lewego górnego rogu).
Powstają w arkuszu jakby trzy prostokąty, jeden to ten narysowany, dwa pozostałe będą teraz twoimi dwoma podarkuszami o wymiarach \(\displaystyle{ A_1(x-a_1, y) A_2(x, y-b_1)}\).

Następny prostokąt rozpatrujesz w tych dwóch arkuszach, następny w trzech, następny w czterech i tak dalej.

Zapomniałem o części wspólnej kolejnych podarkuszy... W tym wypadku trzeba by jeszcze ją jakoś tak rozpatrzyć, aby przy zarysowaniu jej w jednym podarkuszu, usunąć ją z pozostałych, inaczej nie zadziała.

[damkur88]

Hmm no nie wiem... ja myślałem zastosować jakieś drzewo poszukiwań

[abc666]

aby kolejne prostokąty były umieszczane na prostokątach narysowanych wcześniej.

Tak miało być?