[Algorytmy] Cięciwy okręgu

m-2
Użytkownik
Użytkownik
Posty: 55
Rejestracja: 4 maja 2011, o 13:37
Płeć: Mężczyzna
Podziękował: 2 razy
Pomógł: 14 razy

[Algorytmy] Cięciwy okręgu

Post autor: m-2 » 5 sie 2011, o 22:02

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.

Awatar użytkownika
argv
Użytkownik
Użytkownik
Posty: 569
Rejestracja: 27 maja 2009, o 01:27
Płeć: Mężczyzna
Podziękował: 51 razy
Pomógł: 66 razy

[Algorytmy] Cięciwy okręgu

Post autor: argv » 6 sie 2011, o 11:57


ODPOWIEDZ