Pomoc przy zadaniu. Liczenie pola wielu prostokątów.

0

**Na płaszczyźnie umieszczonych jest N prostokątów, które mogą zachodzić na siebie. Należy znaleźć pole figury płaskiej, którą łącznie tworzą wszystkie prostokąty. Liczba prostokątów wynosi od 2 do 100. Współrzędne wierzchołków są liczbami całkowitymi z zakresu od −10000 do 10000. Boki prostokątów są równoległe do osi współrzędnych XY. Dane wejściowe to liczba prostokątów N, podana w pierwszym wierszu, po czym następuje N wierszy, z których każdy zawiera 4 liczby całkowite: a, b, c, d ozna-czające współrzędne lewego dolnego (a, b) oraz prawego górnego (c, d) wierzchołka prostokąta. Liczby te oddzielone są pojedynczymi odstępami. Twój program powinien wypisać jedną liczbę: pole powstałej figury. **

Mam takie zadanie i nie mam pojęcia jak się do niego zabrać, domyślam się, że rozwiązanie jest banalnie proste ale nie mam żadnego pomysłu. Gdyby był ktoś w stanie nakierować mnie na jakieś rozwiązanie byłbym wdzięczny. Głównym problemem dla mnie jest wykrycie gdzie i jak nachodzą na siebie prostokąty. Liczenie samego pola prostokątów w układzie współrzędnych to nie jest problem.

1

Nie jestem ze świata C++, tym niemniej (lub: tym bardziej) dla mnie zadanie nie wygląda na banalnie proste; może na proste, ale to też dla takiej osoby, która już trochę takich rozwiązała.

Zacząłbym jakoś tak: efektywnie interesuje nas jedynie suma pól powierzchni tych części figury, które "wystają", oraz "środka".

Jak ją znaleźć?

  • Te części, które wystają, można znaleźć poprzez znalezienie tych samych współrzędnych o takich samych wartościach dla co najmniej dwóch prostokątów (pamiętaj, że jedną lub dwie wspólne współrzędne może mieć dowolnie dużo prostokątów; przypadek graniczny – wszystkie "zaczynają się" na tej samej prostej).
  • "Środek" można znaleźć, sortując współrzędne dla danej osi i wybierając środkowe.

Nie wiem, czy to dobry trop, ale spróbować można.

2

Dodawaj prostokąty do kontenera.
Każdy nowy sprawdź czy nie ma części wspólnych z innymi prostokątami w kontenerze. Jeżeli ma to wcześniej podziel pokrywające się prostokąty wzdłuż wspólnych krawędzi. Prostokąty
Dodaj te małe prostokąty do kontenera (pamiętając o jednokrotnym dodaniu części wspólnych).
Na końcu po prostu zsumuj pola wszystkich prostokątów.

0

Dzięki za rady, postaram sie jutro jeszcze raz na spokojnie do tego podejść uwzględniając Wasze pomysly moze cos z tego bedzie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1