8030. Stonogi [MWP3_2C1]

tarpauwatratar 2017-12-20 11:58:14 UTC #1

Do tego zadania na starym forum były między innymi: obszerna dyskusja, od groma przykładów, mnóstwo opisanych niuansów, rozszerzony temat jakości testów (obecnie jedynie skromne uwagi pod zadaniem o przypadkach, które występują i nie występują) i chyba nawet jakiś symulator w JS.

Pytanie: czy cokolwiek z tych danych się ostało?

narbej 2017-12-20 21:17:47 UTC #2

Nic mi o tym nie wiadomo, a jaki masz problem z tym zadaniem?

tarpauwatratar 2017-12-20 21:47:34 UTC #3

Zawsze się go bałem, a właśnie postanowiłem się z nim zmierzyć

Na razie przegrywam 1 do 0, ale celowo - chciałem mieć kod dostępny przez SPOJa na każdym komputerze.

narbej 2017-12-21 00:05:00 UTC #4

A więc jednak sukces Teraz kod jest już w clastrze - chmurce i dostępny na każdym dowolnym twoim komputerze podłączonym do niego/niej.

A tak serio, w tamtym wątku o ile pamiętam napisałem, że spora podpowiedź jest w książce: Polya: Jak to rozwiązać -> https://ksiegarnia.pwn.pl/Jak-to-rozwiazac,68427818,p.html, miałem kiedyś tą książkę w rękach wypożyczoną z biblioteki, ale już po fakcie, po uzyskaniu AC własnym, tradycyjnym sposobem.

Co do testów, to problemem może być pytanie jak zakwalifikować kolizję na granicy obszaru i czy uwzględniać błąd - [nie]dokładność obliczeń numerycznych - np EPS = 10e-9 oraz to samo przy obliczaniu czasu kolizji. Można to samemu sprawdzić, wysyłając na spoja różne wersje, ale w tym momencie takich kombinacji wersji trochę się “robi”, chociaż nie aż tak dużo . Możesz też sam przygotować odpowiedni test[y] i zapytać o wynik uzyskany programem AC.

tarpauwatratar 2017-12-21 08:43:56 UTC #5

Kojarzę pozycję, ale nie miałem z nią do czynienia. Przynajmniej jak na razie

Jedna z x rzeczy, których nie jestem pewien, ale x systematycznie maleje w miarę rozważania kolejnych trudności i badania testów assertami

Gdy dzisiaj (z ledwością) wstałem z łóżka, “EPS = 10e-9” było moją pierwszą myślą

Szczerze mówiąc nie widzę innej metody na testowanie niepewności i wątpliwości. Chyba, że znajdę duży plac i stonogi o różnych wymiarach i prędkościach

To ewentualnie w przyszłości. Wszak z tym zadaniem niewątpliwie trzeba się pomęczyć. Cytując komentarz sprzed kilku lat: “(…) ja nie pierwszy na tym zadaniu kończyłem łatwe. (…) faktycznie - sporo kodowania” @j4rooo alias Jaroslaw Konczak

Faktycznie, znalazłem podpowiedź (http://delta.mimuw.edu.pl/artykuly/delta1209/20091208-recenzja.pdf)

mariusz193 2017-12-21 09:12:07 UTC #6

Nie pamiętam, jak rozwiązywałem to zdanie, ale widzę że AC dostałem za pierwszym razem
A patrząc na kod (długi jak na łatwe zadanie, 120 linii, ale sporo zajęły definicje struct), widzę, że nie uwzględniałem żadnych złośliwych przypadków

tarpauwatratar 2017-12-21 09:26:57 UTC #7

Więc może faktycznie wystarczy pomyśleć? W wolnym czasie zacznę to rozwiązywać na poważnie, bo póki co mi się nie chce / nie mam czasu myśleć nad stonogami i opiszę moje wrażenia na forum. I tak w najbliższym czasie muszę napisać długiego posta, do którego napisania zbieram się od pół roku - stonogi będą dobrą rozgrzewką

narbej 2017-12-21 10:31:01 UTC #8

Nie, nie znalazłeś, to jest tylko streszczenie i recenzja i to stosuje się jhako bardzo ogólne podejście do rozwiązywania dowolnego [nie tylko matematrycznego] problemu. Możesz zapomnieć o stonogach i pomyśleć [wyobrazić sobie] o kolizji dwóch jednostek pływających, lub nawet dwóch pojazdów kosmicznych [poruszających się w jednej, wspólnej płaszczyźnie 2D, jeżeli nie podobają Ci się stonogi.

I tak, jest w tej książce taka podpowiedź [nie gotowy algorytm], ale po prostu, trzeba wziąść ją do ręki [rąk] i ją przeczytać, a nie recenzje czy streszczenia, które powinny tylko zachęcać do tego.

tarpauwatratar 2017-12-21 11:12:40 UTC #9

Na razie myślę o dwóch odcinkach, których współrzędne początkowe i końcowe znam i które leżą na dwóch prostych. Jeżeli proste te przecinają się w punkcie leżącym na planszy, oznacza to, że nie mogę wyświetlić “Nie” i muszę rozpatrzyć kolejne kryterium - czas, w którym poruszające się odcinki znajdą się w punkcie przecięcia. W tym celu wyznaczam czas dotarcia do punktu przecięcia początku i końca każdego z odcinków, a następnie rozpatruje utworzone w ten sposób przedziały czasu - jeżeli nachodzą one na siebie, oznacza to, że doszło do zderzenia.

Znając życie intuicja fenomenalna, ścisły opis matematyczny wypada nieco gorzej (np. jeszcze nie znalazłem czasu na rozpatrzenie dwóch odcinków leżących na jednej prostej, a poza tym równanie prostej pionowej nieco różni się od klasycznego y = ax + b), a implementacja to istne czary Niemniej mam nadzieję, że rozwiązywać problemy umiem

tarpauwatratar 2017-12-25 15:02:34 UTC #10

A jednak nie mam pojęcia, co jest nie tak…

Proszę o pomoc np. w postaci outputu dla poniższych testów. Niektóre z nich mogą nie mieścić się w dopuszczalnych zakresach, ale wymyślanie wszystkiego tak żeby było ok nie jest zadaniem trywialnym.

18
3 7 2 7 1
-100 3 20 3 5
2 2 4 2 2
-90 100000 90 100000 100
1 100000 -5 100000 3
1 -100000 -5 -100000 3
3 0 5 0 3
10 -100000 12 -100000 4
3 7 3 -7 2
0 -5 0 5 1
100000 3 100000 4 7
-100000 2 -100000 7 1
0 7 0 -7 1
-1 -1 -1 1 1
-100000 3 -100000 4 2
-99999 2 -99999 3 1
0 1 7 8 3
-3 -3 5 5 7
1 0 2 100000 3
0 100000 -1 0 2
1 10 -1 4 2
3 -91 -30 -190 5
10 66670 -8 66664 1
0 60000 -5 59998 2
-10 60006 0 60000 3
0 -200000 -5 -200010 4
0 0 -1 1 5
5 99990 0 100000 6
8 -99972 0 -100000 7
3 -100005 0 -10000 8
0 0 -100 100 9
10 49995 100 49950 10
0 100000 1 100002 11
0 100000 1 100001 12
0 -99999 1 -99997 1
4 25004 -4 24998 2

Mój out to same NIE.

5
-1 1 -5 5 2
1 1 2 2 3
-1 1 -5 5 2
1 1 2 2 15
-1 1 -5 5 2
-1 -1 -2 -2 3
-1 1 -5 5 2
2 2 1 1 3
-1 1 -5 5 2
-2 -2 -1 -1 3

Wg mnie:

TAK
NIE
TAK
NIE
NIE

mariusz193 2017-12-25 20:14:14 UTC #11

dla pierwszego zestawu:
15 i 17 - TAK

drugi zestaw potwierdzam

a klasyczne równanie prostej ma postać: ax + by + c = 0 (co prawda wtedy może być wiele różnych równań dla jednej prostej, ale nie trzeba się przejmować, czy przypadkiem nie jest to pionowa)

tarpauwatratar 2017-12-26 00:21:05 UTC #12

Dla 17 też mam TAK (błąd w pliku z testem), zaś 15 po rozrysowaniu nie ma sensu - stonogi zaczynają w pozycji, gdzie jedna stonoga przecina drugą… cóż, szukam dalej.

Może tutaj coś jest nie tak?

17
0 5 0 8 3
1 1 3 3 1
0 8 0 5 3
1 1 3 3 1
0 5 0 8 3
3 3 1 1 1
0 8 0 5 3
3 3 1 1 1
0 5 0 8 3
1 1 3 3 5
1 1 3 3 1
0 5 0 8 3
0 5 0 8 3
5 0 8 0 3
0 8 0 5 3
5 0 8 0 3
8 0 5 0 3
0 8 0 5 3
5 0 8 0 3
0 5 0 8 3
0 5 0 8 3
1 -1 3 -3 1
0 8 0 5 3
1 -1 3 -3 1
-5 0 -1 0 1
0 5 0 8 1
-1 0 -5 0 1
0 5 0 8 1
-1 0 -5 0 2
0 5 0 8 1
-1 -1 -3 -3 1
1 -1 3 -3 1
-1 -1 -3 -3 1
1 -1 3 -3 3

Out:

TAK
NIE
NIE
NIE
NIE
TAK
TAK
NIE
NIE
TAK
TAK
NIE
NIE
TAK
NIE
TAK
TAK

Szczerze mówiąc moja pomysłowość jest na wykończeniu. Może ktoś ma jakiś pomysł na test?

Wstawione przeze mnie testy są prawidłowe Policzone w pamięci (choć może bardziej wyobrażone) + program AC.

Zawsze brakowało mi wątku o stonogach na nowym forum, ale jak się okazało niesłusznie. Zadanie jest w gruncie rzeczy bardzo proste, a jedyną przyczyną moich trudności była moja własna głupota, która kazała mi demonizować to zadanie w takim stopniu, że zostawiłem je sobie na koniec i do tego zacząłem od copy-pastowania rozpatrującego wszystkie 10 możliwych przecięć bądź pokryć prostych (proste podzieliłem na poziomą, pionową i ukośną). Skoro już jednak to zrobiłem, mogłem wyassertować kilka rzeczy więc z całą pewnością mogę wam powiedzieć, że:

(nie zaszkodzi powtórzyć ) nie należy wspominać całego mrowia postów z poprzedniego forum, jeżeli ktoś je jeszcze pamięta - ten bagaż należy zostawić przed wejściem na plac ze stonogami (alias @mariusz193 miał rację)
Stonogi Pani Marii Sędzispoj to gatunek tak szybki, że nawet Jaś nie uchwyci, czy znajdują się one na granicy obszaru rozgrywki czy też nie. Z tego powodu nie należy oczekiwać złośliwych testów ze stonogami na granicy obszaru (a przynajmniej mój kod przechodzi dla obszaru mniejszego / większego bądź równego czemuś + EPS i dla obszaru mniejszego / większego od czegoś)
Zawodnicy nie są głupi i wiedzą, że dwie stonogi pędzące na siebie to pewna kraksa. Z tego powodu nie zdarza się, aby dwie stonogi poruszały się po jednej prostej.

Ostatecznie mój kod uprościłem z 10 do zaledwie 3 przypadków, w których kolejnymi dość oczywistymi (dla mnie) ifami analizuję np. czy doszło do przecięcia torów ruchu stonóg. Złożoność logiczna zadania jest więc przeciętna jak na łatwe, ewentualnie lekko powyżej przeciętnej. Złożoność programistyczna jest elementarna - osobiście ułatwiłem sobie kodowanie poprzez numeric_limits::infinity(), ale bool is_inf zrobiłby to samu i wymusił napisanie nie więcej niż 10 dodatkowych linii kodu.