Matematyka.pl

Rozważmy \(\displaystyle{ n}\) cięciw okręgu (każda z nich jest wyznaczona przez swoje końce). Zaprojektuj algorytm działający w czasie \(\displaystyle{ O(n\log_{2}n)}\) obliczający liczbę par cięciw, które przecinają się wewnątrz okręgu. (Jeśli na przykład wszystkich \(\displaystyle{ n}\) cięciw to średnice przecinające się w środku okręgu, to poprawną odpowiedzią jest \(\displaystyle{ {n \choose 2}}\).) Możesz przyjąć, że żadne dwie cięciwy nie mają tego samego końca.

Zadanie pochodzi z "Wprowadzenia do algorytmów" z rozdziału Dynamiczne statystyki pozycyjne.

Strona 5