Otoczka wypukła

01.12.2011 - Michał Karpiński
TrudnośćTrudność

Otoczka wypukła w trzecim wymiarze

Dotychczas zajmowaliśmy się problemem otoczki wypukłej tylko w dwóch wymiarach. Spośród większych wymiarów najbardziej interesujący jest wymiar trzeci. Nie można się nie zgodzić, że otoczka wypukła w trzecim wymiarze posiada duże znaczenie w różnych dziedzinach np. grafice komputerowej.

Na całe szczęście nie trzeba od nowa rozpatrywać naszego problemu tylko dlatego że zwiększyliśmy przestrzeń, w której się poruszamy. Okazuje się, że niektóre algorytmu działające na płaszczyźnie - po drobnych modyfikacjach - nadają się do szukania otoczki wypukłej w 3D (a nawet 4D, 5D itd.). Dla przykładu rozważmy algorytm pakowania prezentu.

Otoczka w trzecim wymiarze będzie wielościanem wypukłym. Na początku załóżmy, że żadne cztery punkty nie leżą na jednej płaszczyźnie. Dzięki temu założeniu uprościmy sobie robotę, bo każda ze ścian otoczki będzie trójkątem. Jak pamiętamy z pierwszej strony: najpierw szukaliśmy punktu startowego. Tym razem będziemy szukali odcinka startowego. Od niego będziemy zaczynali "owijać" zbiór punktów szukając takiego punktu, który wraz z odcinkiem startowym utworzy trójkąt. Poszukiwany przez nas trójkąt musi spełniać taką własność: wszystkie punkty (różne od wierzchołków danego trójkąta) muszą znajdować się po jednej stronie względem tego trójkąta. Dostrzegamy podobieństwo do szukania otoczki w 2D. Trójkąt, który wybraliśmy na pewno należy do otoczki. Powtarzamy krok dla wszystkich odcinków trójkąta, dopóki figura się nie zamknie.

Drugą znaną nam metodą, którą w łatwy sposób można przekształcić jest metoda przyrostowa. Pamiętamy, że w 2D, w każdym następnym kroku wybieraliśmy punkt i szukaliśmy krawędzi otoczki, które są widoczne z tego punktu. Usuwaliśmy te krawędzie i łączyliśmy dany punkt z resztą otoczki. W trzecim wymiarze jest bardzo podobnie: wybieramy punkt i szukamy ścian otoczki, które są widoczne z tego punktu; usuwamy je i dołączamy punkt do reszty otoczki.

O otoczce wypukłej można by dużo opowiadać. Niestety zajęłoby to więcej miejsca niż tych kilka stron. W tym artykule przedstawiłem podstawowe informacje z dziedziny geometrii obliczeniowej, które pomogą początkującym mistrzom algorytmiki w poszerzaniu swoich horyzontów. Na koniec, aby utrwalić poznaną wiedzę, zapraszam do rozwiązania kilku zadań programistycznych.

Zadania ze sprawdzaczką

Zadanie 1 - "Strefy wpływów"

W pewnym mieście znajduje się wiele sklepików spożywczych, a każdy z nich należy do innej sieci. Jeśli spojrzymy na mapę miasta z lotu ptaka, to łatwo odnajdziemy tzw. strefę wpływów dla danej sieci. Strefę wpływów dla ustalonej sieci $ A $ definiuje się jako obszar ograniczony przez najmniejszy wielokąt zawierający wszystkie sklepiki sieci A. Innymi słowy, jeśli przyjmiemy, że sklepiki sieci $ A $ są zbiorem punktów na płaszczyźnie, to jej strefa wpływów jest jej otoczką wypukłą.

Właściciele wszystkich sieci w mieście ustalili, że nie będą sobie wchodzić w drogę i będą tak rozmieszczać swoje sklepy, aby ich strefy wpływów na siebie nie zachodziły.

Pewnego pięknego dnia właściciele spostrzegli, że sklepów spożywczych jest w mieście zbyt wiele przez co konkurencyjność poszczególnych firm spada. Razem ustalili, że połączą się w jedną wielką firmę. Połączeń będą dokonywali stopniowo w określonej kolejności. Każde połączenie zwiększy strefę wpływów.

Tutaj pojawia się problem: po powiększeniu strefy wpływów dwóch kolejnych firm powstaną niepotrzebne sklepy, czyli takie, które leżą wewnątrz (lub na krawędzi) nowej strefy wpływów. Nie mają one wpływu na daną strefę, więc należy je zamknąć.

Na rysunku powyżej najpierw łączymy strefy firm czerwonej i niebieskiej. Zauważmy, że powstały dwa niepotrzebne sklepy. W kolejnym kroku dołączamy strefę zieloną. Wszystkich niepotrzebnych sklepów jest razem pięć.

Twoim zadaniem jest ustalenie łącznej liczby niepotrzebnych sklepów po każdym kroku łączenia dwóch kolejnych firm. Możesz przyjąć następujące założenia:

  • przed pierwszym połączeniem nie ma niepotrzebnych sklepów
  • kolejność łączenia jest podana tak, aby po kolejnym połączeniu wszystkie strefy wpływów dalej na siebie nie zachodziły
  • "nowa strefa" jest tylko jedna tzn. każdą kolejną strefę dołączamy do poprzednio utworzonej

Wejście

W pierwszej linii wejścia podana jest liczba $ N $ ($ 1<N<100 $) oznaczająca liczbę sieci sklepów. Ustalamy, że każda sieć otrzymuje unikalny numer ze zbioru $ \{1..N\} $. W kolejnej linii podanych jest $ N $ liczb oddzielonych spacją, które oznaczają kolejność łączenia stref. Następnie podane są definicje $ N $ stref. W $ i $-tej definicji wyznaczamy strefę $ i $-tej sieci. W pierwszej linii definicji podana jest liczba $ M $ ($ 2<M<100 $) oznaczająca liczbę sklepów $ i $-tej sieci. W drugiej linii znajduje się $ 2M $ liczb z przedziału $ [0,10000] $ oddzielonych spacjami. Każde $ M $ kolejnych par liczb wyznacza punkt $ (x,y) $ w układzie współrzędnych, który określa położenie sklepu na mapie. Punkty strefy są podane w kolejności przeciwnej do ruchu wskazówek zegara.

Wyjście

Wyjście składa się z jednej linii. Należy wypisać $ N-1 $ liczb oddzielonych spacjami. Każda z nich oznacza liczbę niepotrzebnych sklepów po połączeniu dwóch kolejnych stref zgodnie z kolejnością podaną na wejściu.

Przykład 1

Wejście:
3
1 2 3
3
0 0 1 1 0 3
3
3 2 1 0 4 3
4
2 4 3 4 3 5 2 5

Wyjście:
2 4

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com