612. Wyścigi biedronek [ETI06E3]

[turas]

Hej,
mógłby ktoś się podzielić testami dla tego zadania? Program zdaje testy przykładowe oraz te wymyślone przeze mnie, jednakże SPOJ wyświetla błędną odpowiedź. kod programu
Byłbym wdzięczny za wszelkie sugestie i przepraszam za zagmatwany kod

[narbej]

mógłby ktoś się podzielić testami dla tego zadania?

Tylko 6 osób zrobiło to [trudne? ] zadanie, dawno temu, więc mało prawdopodobne, że się ktoś podzieli, ale dzięki twojemu pytaniu, może teraz zmobilizuje to innych do zmierzenia się z nim.

PS
Co do twojego kodu.
Jeżeli już, to zamiast float, użyłbym double, ale w tym zadaniu jest to moim zdaniem całkowicie zbędne. Wystarczy typ całkowity. Nie musimy obliczać współrzędnych punktu kolizji, a tylko czy taki fakt zaistnieje czy nie. W twojej klasie owad, moim zdaniem ilość kolizji to za mało. Ja dodałbym jeszcze z kim [wektor z nr biedronek]. Wtedy można nawet ewentualnie zrezygnować z ilości, a tą informacją będzie rozmiar vektora. [vector.size() == 0 brak kolizji]. W twoim kodzie jest co najmniej dwukrotne sortowanie, jedno w pętli? więc pewnie dużo więcej. Ja [jak już będę robił] raczej użyję odpowiedniej kolejki . [i tak pewnie za dużo podpowiadam]. Wykryć kolizję można porównując tylko znak dwóch wyznaczników, jeżeli oba są dodatnie lub ujemne i różne od zera to kolizji na pewno nie ma. Czy jest kolizja, trzeba pewnie [tak myślę] porównać jeszcze odpowiednie znaki następnych 2 wyznaczników. Na początek zakładamy, że wszystkie biedrony startują [są dopuszczone] i odejmujemy po jednej najbardziej kolizyjnej jeżeli takie są. Jest tu pewien haczyk, jak modyfikować, w jaki sposób, kolejkę, ale myślę, że tu trzeba na to samemu wpaść - zresztą mogę się mylić, jeszcze nie mam ani AC ani nawet nie rozpocząłem kodowania.

PS 2
Zamiast:

vector <owad> biedronka;

cin >> ilosc;
biedronka.reserve(ilosc);

można chyba?:

 cin >> ilosc;
 vector <owad> biedronka(ilosc);

a potem
biedronka[i] = owad(xs, xf, yf); // może całość nie szybciej, ale 'ładniej' i krócej

zamiast:

for (int j = i; j < ilosc; ++j)
	{
		if ((i != j) && (

można:

for (int j = i + 1; j < ilosc; ++j)
		{
			if (....  // zbędny warunek (i != j) &&

[turas]

Dzięki za zainteresowanie tematem i rady
Jesteś pewny, że nie trzeba obliczać punktu kolizji? Trasy mogą się chyba też przeciąć za metą...

[narbej]

Zacząłem próbować robić to zadanie, ale na razie WA. Według mnie kolizje dotyczą tylko kolizji odcinków start meta, a nie prostych, na których leżą te odcinki. I ja w moim algorytmie nie obliczam współrzędnych takich punktów, tylko odnotowuję sam fakt istnienia kolizji [lub kilku kolizji] dla każdego odcinka. Ale jak napisałem wyżej na razie WA, chociaż testy przykładowe oczywiście ok

[turas]

Też uważam, że kolizje dotyczą tylko odcinków start - meta. Tylko, jeśli nie policzę współrzędnych kolizji, mogę niepoprawnie odrzucić np. biedronkę, której prosta, na której leży odcinek start - meta przecina się z prostą innej biedronki, lecz same odcinki start - meta się nie przecinają. Przynajmniej tak mi się wydaje

[narbej]

Oczywiście masz rację, ale...
1. Musisz ten punkt przecięcia [ob]liczyć na współrzędnych rzeczywistych [dużo lepiej i szybciej na double niż float]
2. Musisz sprawdzić, czy obliczony pkt kolizji [przecięcia] znajduje się pomiędzy pkt startu i mety jedenj biedronki i jednocześnie pkt startu i mety drugiej biedrony.

Zamiast tego można określać, po której stronie prostej leżą pkt http://www.matematyka.pl/264419.htm, ale trzeba to zrobić [maks] dla dwu prostych i dwu pkt i porównywać znak wyznacznika. Razem więc trzebaby policzyć [maks] 4 wyznaczniki ale to chyba mimo wszystko łatwiej i szybciej? Dlaczego maks 4. Bo jeżeli policzymy det dla jednej prostej [odcinka - pierwszej biedrony] i dwu pkt start, meta drugiej i okaże się, że oba det są tego samego znaku i != 0 , to nie ma kolizji. W przeciwnym wypadku, musimy jeszcze sprawdzić biorąc drugi odcinek [start meta drugiej biedrony] -wyznaczający prostą i położenie startu i mety [pierwszej biedrony] względem tej prostej.

[turas]

Faktycznie, ten sposób wydaje się dużo lepszy:)
Jednakże problem chyba tkwi gdzieś jeszcze, bo podobnie jak u Cb, dalej WA...

[narbej]

Dodatkowo, można uwzględnić, że wszystkie biedrony startują z linii y = 0.
Czyli dla bied1 i dla bied 2 - pkt startu, będzie to macierz:
1 x1 0 //pkt start biedr 1
1 x2 y2 //pkt mety biedr 1
1 x3 0 //pkt startu biedr 2

oraz jak wyżej ale dla mety:
1 x1 0 //pkt start biedr 1
1 x2 y2 //pkt mety biedr 1
1 x3 y3 //pkt mety biedr 2

Problem polega na znalezieniu odpowiedniego prostego testu, który pokaże, że eliminowanie najbardziej kolizyjnych [mających najwięcej kolizji] biedron nie zawsze jest najlepszym algorytmem. Dokładniej, gdy jest kilka biedron o jednakowej "kolizyjności" to czy zawsze nie ważna jest kolejność ich eliminacji. DOdatkowo, wielokrotne sortowanie, nawet tylko 200 biedron, może być za wolnym algorytmem.

[narbej]

NP. taki sobie skromny teścik:
5
0 1 1
4 5 1
2 1 1
4 3 1
2 3 1

poprawny wynik:
3

A może być takich podobnych, ale bardziej skomplikowanych całe multum.

[turas]

Pomyślałem, że może w przypadku biedronek o takiej samej kolizyjności usunąć najpierw tą, która najmniej razy koliduje z innymi o tej samej, maksymalnej kolizyjności. Czyli w podanym przez Cb przykładzie: /\/\/ najpierw usunąć biedronkę drugą albo czwartą. Wtedy otrzymuję poprawny wynik w tym przykładzie, jednak to nie wystarcza. Pewnie jest jeszcze inny zestaw danych, dla którego moje myślenie się nie sprawdza...

[narbej]

Więc powinieneś albo znaleźć ten zestaw danych, albo zmienić myślenie [ja też]. To drugie wydaje się nawet dużo łatwiejsze. We Wprowadzenie do algorytmów, w dziale geometria obliczeniowa jest przedstawiony algorytm wyszukiwaniazliczania ilości przecięć odcinków, za pomocą przesuwającej się linii pionowej [Intersections of a Set of Segments; sweep line algorithm; ] Dotyczy on odcinków nie mających wspólnych końców, więc trzebaby go "trochę" zmodyfikować-dostosować do biedronek, ale myślę, że gra warta nie świeczki, a może nawet warta AC