Zaawansowane algorytmy i struktury danych/Ćwiczenia 12

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy trzy lub więcej odcinków przecina się w tym samym punkcie.

Rozwiązanie

Zadanie 2

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy obecne są pionowe odcinki, a ich dolne końce traktujemy jako lewe końce, a górne końce jako prawe. Położenie odcinków w porządku na miotle wyznaczamy na podstawie współrzędnej dolnego końca.

Rozwiązanie

Zadanie 3

Masz dane dwa zbiory punktów oraz . Zakładamy, że w sumie tych zbiorów nie ma trzech współliniowych punktów. Pokaż, że można dobrać w pary punkty do punktów w tak aby utworzone w ten sposób odcinki się nie przecinały. Zaproponuj algorytm wyznaczający takie parowanie.

Rozwiązanie