Witam. Od poniedziałku próbuję rozwiązać jedno zadanko algorytmiczne, jednak moja cierpliwość co do szukania błędów i haczyków wyczerpała się. Dlatego zwracam się z prośbą o pomoc do Was.Jak rozwiązalibyście to zadanie http://www.spoj.com/WIPING5/problems/WIPING58/ ? Ogólnie wpadłem na pomysł, aby znajdować punkty z którymi prosta opisująca promień ma rozwiązania z prostą opisująca odcinki. Oczywiście, rozwiązanie musi należeć do odpowiedniego zakresu, w przypadku gdy mamy więcej niż jeden punkt, wybieram najbliższy. Potem promieniem jest prosta prostopadła do prostej opisującej promień przechodząca przez wybrany punkt.Natomiast, w którą stronę odbije się promień obliczam z położenia punktu względem prostej Mam wrażenie, że można to jakoś dużo prościej zrobić, ale niestety nie mam pomysłu.
Asthean napisał(a):
gdy mamy więcej niż jeden punkt, wybieram najbliższy
A dlaczego tak? Nie widzę w zadaniu opisu, co robić w sytuacji, gdy promień trafi w zwierciadło dokładnie z boku.
Asthean napisał(a):
Potem promieniem jest prosta prostopadła do prostej opisującej promień przechodząca przez wybrany punkt
A dlaczego tak? Jak dla mnie trzeba użyć użyć zasady, że kąt padania równa się kątowi odbicia.
Hmm, z tego co widać
1 1 oznacza, że punkt to x = 1 i y = 1
a kolejne 1 0 oznacza, że porusza się x, a y się nie zmienia, czyli takich kombinacji jest tylko 4 wystrzeliwania lasera.
Musisz policzyć czy laser znajduje się w punktach określonych funkcjami liniowymi z ograniczeniem zbioru zwierciadła tzn. szerokości.
Liczysz punkt przecięcia prostych, lasera ze zwierciadłem.
Jeśli y zwierciadła rośnie i y lasera rośnie to przy rośnięciu x laser skręci w prawo, a tak w lewo itp.
Teraz jak liczysz kąt odbicia lasera to wystarczy, że znasz obie funkcje zwierciadła i lasera, i odwrócisz lasera o 180 stopni i masz kąt odbicia jaki będzie funkcji po kolizji z lustrem.
edit, tam miało być 8 kombinacji gdyż laser nie może stać w miejscu,
I lustrzane odbicie funkcji to wyliczenie prostopadłej do punktu przecięcia zwierciadła z laserem + rośnięcie w kierunku wyliczonym wcześniej.
Uczynny Mleczarz napisał(a):
edit, tam miało być 8 kombinacji gdyż laser nie może stać w miejscu,
I lustrzane odbicie funkcji to wyliczenie prostopadłej do punktu przecięcia zwierciadła z laserem + rośnięcie w kierunku wyliczonym wcześniej.
Masz daną prostą, po której leci laser, więc sprawdzasz tylko przecięcie z tymi zwierciadłami (odcinkami),
na których ta prosta się zmienia - zgodnie zasadami odbicia... no to tyle.
Prostacki problem o złożoności: n^2, n - liczba odcinków/zwierciadeł.
Trzeba uwzględnić jakiś limit tych odbić, np. 1000, ponieważ możliwe są pętle, np. taka:
|<-----laser sobie lata w nieskończoność-------->|
Warunek pętli trochę inaczej wygląda: punkt i kierunek należy tu uwzględnić, czyli w sumie prostą po której leci laser...
więc należałoby to pamiętać i sprawdzać, czy się nie powtarza.
Niemniej i tak jest możliwe odbijanie pod niewielkim kątem pomiędzy dwoma lusterkami,
np. kąt: 0.001 dałby aż coś rzędu 1000 odbić, dla dwóch równoległych odcinków-lusterek o długości 1.0, i w odległości 1,
zanim wyleciałby poza brzeg lustra.
a jeśli jakieś zwierciadła będą zawierać się w każdym boku tego samego n-kąta foremnego ? Mamy wtedy sytuację odbijania się pod niewiele różniącym się kątem między n zwierciadłami.
Powinniśmy jeszcze móc wykryć sytuację, kiedy promień światła zostanie uwięziony między n-zwierciadłami. Współczynniki odpowiadających sobie promieni światła w każdym cyklu odbijania będą do siebie bardzo podobne. Najprościej :
|A_{k}-A_{k+n}| <= ΔA i | B_{k}- B_{k+n}| <=ΔB
Jeśli ten warunek zostanie spełniony to promień światła jest uwięziony. ΔA i ΔB powinny wynikać z błędu reprezentacji liczby zmiennoprzecinkowej.