CERC 2010: Szkice rozwiązań

28.11.2010

A: Ardenia

Treść (pdf) | wyślij rozwiązanie.

W tym zadaniu należało obliczyć odległość między dwoma odcinkami w przestrzeni trójwymiarowej. Niech P0 i P1 będą końcami pierwszego odcinka, zaś Q0 i Q1 drugiego. Zacznijmy od wyznaczenia liniowych funkcji P i Q, takich że P(0) = P0, P(1) = P1, Q(0) = Q0 i Q(1) = Q1. Będziemy używać również P i Q dla oznaczenia odcinków, a p i q dla oznaczenia odpowiadających im wektorów, tj. p = P(1) - P(0) and q = Q(1) - Q(0).

Na początku potrzebna nam będzie geometryczna procedura wyznaczająca odległość między punktem A a odcinkiem P. Zauważmy, że odległość ta jest równa minimum funkcji d(P(x),A), gdzie d jest odległością między dwoma odcinkami a x jest z przedziału [0,1]. Zatem zaprogramowanie tej procedury to prosta minimalizacja funkcji. Tak naprawdę moglibyśmy rozszerzyć to podejście i rozwiązać właściwy problem: należy znaleźć minimum funkcji d(P(x), Q(y)), gdzie x i y są z przedziału [0,1]. Można je wyliczyć używając pochodnych, choć jest to trochę bardziej skomplikowane niż minimalizacja funkcji jednowymiarowych.

Zaprezentujemy tutaj inne, bardziej algebraiczne podejście (którego zaletą jest to, że działa również w przestrzeniach o większej liczbie wymiarów). Na początku sprawdźmy, czy odcinki są równoległe. W takim przypadku zadanie ogranicza się do znajdowania odległości między punktem a odcinkiem i sprawdzaniem paru warunków brzegowych. W przeciwnym przypadku odcinki są nierównoległe i możemy odnaleźć parę najbliższych punktów P(x) i Q(y), gdzie x i y są dowolnymi liczbami rzeczywistymi. Wykorzystujemy tutaj fakt, że dla nierównoległych odcinków punkty te są jednoznacznie wyznaczone, a odcinek (P(x),Q(y)) jest prostopadły jednocześnie do P i Q. Zapisując ten odcinek jako wektor w = P(x) - Q(y) otrzymujemy równania w · p = 0 oraz w · q = 0, gdzie kropka oznacza iloczyn skalarny. Mamy zatem dwa równania, z których musimy wyznaczyć dwie niewiadome: x i y. Następnie wystarczy sprawdzić czy P(x) i Q(y) leżą w odcinkach P i Q, czyli czy x i y należą do przedziałów [0,1]. Jeśli są poza nimi, odległość jest minimalizowana przez punkt końcowy jednego z odcinków.

Informacje dodatkowe

Na wielu zawodach ACM jedno z zadań jest zadaniem na zmęczenie zawodników. Przykładem jest implementacja parsera trudnej gramatyki: wiele osób wie, jak to zrobić, ale napisanie działającego programu zajmuje dużo czasu. Drużyna, która zabierze się za takie zadanie nie robi już zazwyczaj żadnego innego (może poza najłatwiejszym).

Zadanie A, którego nie zrobiła na naszych zawodach żadna drużyna, stało się wbrew naszym oczekiwaniom i zamiarom takim właśnie zadaniem.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com