Urodziny

Z okazji urodzin (swoich), proponuję zadanie (cudze) o cięciu tortu. Zadanie jest w zasadzie z geometrii, lecz główną trudnością nie będzie implementacja, ale przekonanie się, że optymalne rozwiązanie ma pewną prostą strukturę, no i odrobina prostych rachunków. Tortu, niestety, nie oferuję, ale zadanie będzie naprawdę apetyczne!

Treść zadania jest tutaj. Dostajemy n kół na płaszczyznie. Wolno nam wykonać k cięć, każde z nich może być dowolną prostą. Pytanie jest dość naturalne: jaka jest największa możliwa sumaryczna liczba kawałków, które możemy utworzyć wykonując takie cięcia? Jeśli k=0, nie mamy zbyt wiele możliwości, i odpowiedź to po prostu n. Jeśli n=1, zadanie redukuje się do popularnego ćwiczenia, w którym pytamy się o największą liczbę obszarów, które można utworzyć rysując k prostych na płaszczyźnie. Jeśli zaś k>0 i n>1… robi się ciekawie. Na pocieszenie, podane koła są rozłączne (ściśle, czyli nie mogą się nawet dotykać).

Może zacznijmy od wspomnianego ćwiczenia. Wyobraźmy sobie, że dodajemy kolejne proste, zaczynając od pustej płaszczyzny, i zliczamy nowo utworzone obszary. Na samym początku mamy oczywiście tylko jeden obszar. Pierwsza prosta podzieli go na dwa mniejsze. Druga prosta może jedynie przeciąć tę pierwszą i utworzyć dwa kolejne obszary. Trzecia prosta może przeciąć dwie poprzednie i utworzyć trzy obszary. No i tak dalej, czyli mając k prostych możemy utworzyć co najwyżej 1+1+2+\ldots+k=1+\frac{k(k+1)}{2} obszarów. Odrobiny zastanowienia wymaga być może to, że faktycznie możliwe jest osiągnięcie takiej liczby, jednak tak naprawdę jedyne, na co trzeba uważać, to wybieranie kolejnych prostych tak, aby żadne dwie z nich nie były równoległe.

Wracając do zadania, dla n=1 odpowiedź to dokładnie 1+\frac{k(k+1)}{2}. Czemu? Przecież nie mamy do dyspozycji całej płaszczyzny, lecz tylko jakieś koło. No, tak czy inaczej powyższe rozumowanie pokazuje, że odpowiedź nie może być większa. Z drugiej strony, mając dany podział płaszczyzny, zawsze można go przeskalować tak, aby zmieścić się w (dowolnie małym) kole. Tę sztuczkę warto zapamiętać: choć prosta, będzie kluczowa w dalszej części rozwiązania.

Spróbujmy przerobić powyższe rozumowanie tak, aby działało dla n>1. Zaczynamy od n obszarów. Zastanówmy się, jak może wzrosnąć ich liczba po dorzuceniu jednej prostej. W dość oczywisty sposób zależy to od podanych na wejściu kół: być może wszystkie są ustawione w jednej linii, i możemy utworzyć aż n nowych obszarów, a być może mimo dużego n jesteśmy w stanie przeciąć tylko kilka kół, a co za tym idzie utworzyć tylko kilka nowych obszarów. Tak czy inaczej liczba nowych obszarów jest równa liczbie przeciętych wnętrz kół (dotknięcie koła w jednym punkcie nie jest dla nas przydatne). Oznaczamy sobie maksymalną taką liczbę przez M.

Teraz zastanówmy się, jak może wzrosnąć liczba obszarów po dorzuceniu drugiej prostej. Znów możemy przeciąć M wnętrz kół i utworzyć dzięki temu M nowych obszarów, lecz teraz mamy dodatkowo szansę na przecięcie pierwszej prostej, co spowoduje utworzenie jeszcze jednego obszaru. A więc maksymalna liczba nowych obszarów to M+1. No to teraz zastanówmy się, ile obszarów może utworzyć trzecia prosta. Znów, dzięki przecięciu wnętrz kół możemy dostać ich M, ale dodatkowo możemy liczyć na przecięcie pierwszej i drugiej prostej, czyli maksymalna liczba nowych obszarów to M+2. Uogólniając to proste rozumowanie dostajemy, że mając k prostych możemy utworzyć maksymalnie

n+M+(M+1)+\ldots+M+k-1=n+\frac{k(2M+k-1)}{2}

obszarów. Odrobinę niepokojąca jest jednak kwestia, czy rzeczywiście można tak dobierać kolejne proste, aby osiągnąć tę liczbę?

Można! Wystarczy tylko przypomnieć sobie sztuczkę ze skalowaniem. Wybierzmy prostą, która przecina M wnętrz kół, i zduplikujmy ją k razy. Ponadto wybierzmy na niej dowolny punkt p, który leży wewnątrz (dowolnego) koła. Teraz wyobraźmy sobie, że minimalnie obracamy każdą z prostych wokół p, przy czym obroty wybieramy tak, aby po jego wykonaniu proste nie pokrywały się. Co prawda p może leżeć dość blisko brzegu koła, ale stosując argument ze skalowaniem łatwo uwierzyć, że w najgorszym wypadku nasze obroty będą bardzo małe (lecz niezerowe!). W podobny sposób można trochę przesunąć każdą prostą (nie zmieniając nachylenia) tak, aby żadne trzy z nich nie przecinały się w tym samym punkcie. Cały proces (dla n=3) jest przedstawiony na poniższej ilustracji.

urodziny1

Opisana wyżej operacja może być przeprowadzona w dowolnie małym otoczeniu p, czyli nie ma ryzyka, że zabraknie nam miejsca. Teraz trzeba tylko zauważyć, że tak naprawdę daje nam to sytuację, w której każda para prostych tworzy nowy obszar.

No dobrze, czyli wiemy już, że do rozwiązania zadania wystarczy znajomość M. Uprośćmy sobie trochę życie i powiedzmy, że interesuje nas maksymalna liczba przeciętych kół (a nie tylko ich wnętrz). Do pierwotnej wersji wrócimy za jakieś 10 minut. Wyobraźmy sobie prostą, które maksymalizuje tę liczbę, i przyjmijmy, że M>1. Skoro interesuje nas przecinanie całych kół, tak długo, jak prosta nie jest styczna do żadnego koła, możemy ją trochę przesunąć (lub obrócić). Tak naprawdę wystarczy więc rozważyć tylko te proste, które są styczne do jakiegoś koła, a nawet (ze względu na to, że proste możemy zarówno przesuwać, jak i obracać) tylko te, które są styczne do przynajmniej dwóch kół. Naturalne jest więc przeiterowanie się wszystkich kołach, i wyznaczenie najlepszej stycznej dla każdego z nich.

urodziny2

Ustalmy koło, którego najlepszą styczną chcielibyśmy wyznaczyć, i dla wygody udawajmy, że jego środek to (0,0), a jego promień nazwijmy R. Taka styczna jest oczywiście jednoznacznie wyznaczona przez swoje nachylenie. Wystarczy nam rozważanie tylko takich nachyleń, które odpowiadają stycznym także do jakiegoś innego koła, można by więc zgadnąć sobie to inne koło, a następnie policzyć ile kół jest przecinanych przez wybraną prostą. Dałoby to rozwiązanie, które działa w czasie \mathcal{O}(n^3), czyli raczej słabo. Kuszące wydaje się uniknięcie tego zliczania dla każdej wybranej prostej z osobna. Zastanówmy się więc, kiedy dane koło powoduje zwiększenie wyniku o jeden?

urodziny3

Prosty eksperyment (myślowy lub taki ze szklanką i długopisem) pozwala na przekonanie się, że każde koło powoduje zwiększenie wyniku na dwóch przedziałach kątowych. Te przedziały można wyznaczyć konstruując styczne do ustalanego koła i tego rozważanego, lecz zostawmy tę (rachunkową) kwestię na później. Cały problem redukuje się więc do następującego: mając dane 2(n-1) przedziały kątowe, znajdź kąt \alpha, który należy do jak największej liczby tych przedziałów. Skoro mowa o kątach, pewnie wato użyć zamiatania kątowego, które przydało nam się już jakiś czas temu: wyobrażamy sobie, że rozważamy coraz większe kąty \alpha, i utrzymujemy liczbę przedziałów, do których należy aktualny kąt. Możemy zacząć od \alpha=0 i wyznaczyć dla niego tę liczbę naiwnie. Następnie przeglądamy kolejne \alpha, dla których ta liczba ma szansę na jakąkolwiek zmianę, czyli tak naprawdę takie, które odpowiadają początkom i końcom przedziałów. Jest tutaj pewna subtelność: co jeśli mamy kilka (lub kilkaset) przedziałów, które kończą się lub zaczynają w tym samym miejscu? Skoro interesuje nas maksymalizacja, pewnie wystarczy rozstrzygnąć takie remisy tak, że najpierw rozważamy początki, a następnie końce. Tak naprawdę potrzebna jest nam tylko posortowana lista wszystkich początków i końców, z remisami rozstrzygniętymi w opisany przed chwilą sposób. Oznacza to, że mamy pomysł, które ma szansę na (poprawne) działanie w czasie \mathcal{O}(n^2\log n), modulo dwa istotne szczegóły: musimy wrócić do kwestii wyznaczenia przedziałów, a następnie uwzględnić to, że w zasadzie wolelibyśmy przecinać tylko wnętrza kół.

Zacznijmy od rachunków. Wygodne okazuje się być rozpatrywanie nie kątów utworzonych przez styczne z osią OX, lecz nachyleń odcinków prostopadłych do stycznych z jednym końcem w (0,0), a drugim na prostej, tak jak na poniższym rysunku.

Dla ustalonego drugiego koła o środku w (x,y) i promieniu r, chcielibyśmy wyznaczyć przedziały nachyleń, dla których styczna przecina to drugie koło. Czyli tak naprawdę interesuje nas wyznaczenie nachyleń, dla których prosta jest styczna do obydwu kół jednocześnie. Jeśli oznaczymy przed \alpha nachylenie odcinka łączącgo (0,0) z (x,y), musimy tylko wyznaczyć kąty \beta i \gamma zaznaczone na poniższej ilustracji. Wtedy szukany przedziały to po prostu [\alpha-\beta,\alpha-\gamma] i [\alpha+\gamma,\alpha+\beta].

urodziny4

  1. Wyznaczenie \beta jest prościutkie. Wystarczy policzyć \text{acos}(\frac{R-r}{\sqrt{x^2+y^2}}).
  2. Wyznaczenie \gamma jest odrobinę bardziej męczące. Popatrzmy na odcinek łączący (0,0) i (x,y) i powiedzmy, że punkt będący przecięciem dwóch krzyżujących się stycznych dzieli go w proporcjach a:b. Z podobieństwa trójkątów dostajemy, że \frac{R}{r}=\frac{a}{b}, więc \sqrt{x^2+y^2}=a+b=a+\frac{r}{R}a, czyli możemy wyznaczyć łatwo a. Następnie należy policzyć \text{acos}(\frac{R}{a}).

Załatwia to kwestia wyznaczenia przedziałów. No i fajne, jest jednak pewien problem. Powiedzieliśmy bowiem, że tak naprawdę interesuje nas przecinanie nie całych kół, lecz tylko ich wnętrz! Dla „losowego” ustawienia kół pewnie nie jest to żadnym problemem, gdyż zawsze można trochę przesunąć (lub obrócić) znalezioną prostą, lecz dość łatwo skonstruować złośliwy przykład, w którym nie jest to możliwe.

urodziny5

Jak poradzić sobie z tą nieoczekiwaną trudnością? Okazuje się, że wystarczy traktować przedziały kątowe jako niedomknięte z jednej strony, czyli [p,q). Udowodnienie poprawności tej (wydawałoby się aż zbyt prostej) modyfikacji pozostawiam Czytelnikowi.

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s