Zadanie - pomoc z algorytmem

master53 [ Senator ]

Niestety nie mam tego profesjonalnie rozrysowanego, a że nigdy nie rysowałem tego typu schematów, to obawiam się, że nie wiele można by było z tego zrozumieć.

eLJot [ a.k.a. księgowa ]

Z Twoich wypocin też niewiele można zrozumieć :P A chyba nie myślisz, że ktoś za Ciebie rozwiąże problem na poważne zawody (chyba nawet ogólnokrajowe)
Możemy pogadać po 7 stycznia ;)

master53 [ Senator ]

eLJot --> Ależ chętnie z Tobą porozmawiam. A więc do wtorku ;)

Może ktoś chciałby udzielić jakiejś małej wskazówki ?

Mazzop [ ]

ja bym z danych wejściowych utworzył 2 tablice - "poziomą" (L i P) i "pionową" (D i G) reprezentujące odcinki, i przy analizowaniu każdego zdjęcia zwiększanie (zliczanie zdjęć pokrywających dany odcinek) odpowiednich elementów w obu tablicach, no i w wejściu będzie max z iloczynu każdy element z tablicy "poziomej" przez każdy z "pionowej"

Mazzop [ ]

a nie, pokręciłem :D, bzdura wyszła

master53 [ Senator ]

No właśnie coś mi się nie zgadzało :)

Scatterhead [ łapaj dzień ]

Mazzop dobrze mysli, zrzutuj sobie te wspolrzedne na poziome i pionowe, dzieki temu lepiej ebdzie kombinowac.

Mazzop [ ]

pomysł zastępczy ze 160 miliardami kwadratów i potem max po nich też coś nie teges :)

master53 [ Senator ]

Na początku myślałem, aby porównać pierwszy zestaw współrzędnych z resztą, jeśli się zgadza to zwiększyć licznik o 1 i tak po kolei, ale jest jeden przypadek, w którym takie rozwiązanie się gubi. Mianowicie jeśli na dane zdjęcie zachodzą 2 inne, ale nie nachodząc na siebie. Czyli zdjęcia 2 i 3 nachodzą na zdjęcie 1, ale nie nachodzą na siebie. Wtedy licznik zliczyłby to błędnie, a przecież nie da się w takim przypadku przypiąć tych 3ch zdjęć jedną szpilką i tu pies pogrzebany.

kamyk_samuraj [ Senator ]

Masz wspolrzedne czterech punktow (zdjecie)
A B

C D
By szpilka wypadla w obrebie zdjecia, to wspolrzedna xszpilki musi byc Ax=<Xszpilki=<Bx (albo Cx<=xszpilki=<Dx) oraz wspolrzedna yszpilki Cy=<Yszpilki=<Ay.

W zadaniu masz dwa rogi - ale, jako, ze zdjecie to prostokat to Ax=Cx, Bx=Dx i tak dalej, wiec nie sa co potrzebne wszystkie.

Scatterhead [ łapaj dzień ]

jeszcze jedna podpowiedz: jezeli sobie zrzutujesz wszystkie zmienne na jedna linie, czyli wszystkie X posortujesz od najmniejszego do najwiekszego z zachowaniem tego ktory z punktow jest koncem a ktory poczatkiem masz prosty algorytm na znalezenie miejsca przeciecia sie najwiekszej liczby kwadratow:

masz licznik M = 0
zmienna X=0 ktora wskazuje na poczatek miejsca gdzie znajudje sie najwiecej miejsc do przeciecia
oraz XX ktora zawiera informacje ile zdjec tam przetniesz maksymalnie

i lecisz od poczatku do konca, zwiekszajac licznik M o 1 jezeli przechodzisz przez punkt poczatku zdjecia lub zmniejszasz o 1 jezeli dochodzisz do konca jakiegos zdjecia. Jezeli zwiekszyles M o jeden i jest to wieksza liczba niz XX to ustawiasz XX na M oraz miejsce X na to w ktorym jestes.

Tym sposobem mozesz przeleciec X i Y, ale musisz jescze polaczyc te dwa wyniki na raz

M@RCO [ Centurion ]

Stary :/ twoje myśli są tak chaotyczne, że szok.
Dobra rada. Porzuć dotychczasowy pomysł i zrób algorytm w postaci schematu blokowego jak to eLJot już pisał. Wtedy możesz nam przekazać swoją myśl. Nikt pozatym nie zrobi Ci czegoś na konkurs stary, jeżeli masz za to laury zbierać a w przyszłości nie będziesz z tego nic wiedział to nie ma sensu -.- wróć z "klockami"

kamyk_samuraj [ Senator ]

Ach - chodzi tylko o maksimum... To masz doradzone w [13]. Zaczalem czytac i od razu pomyslalem, ze na koncu sam wbijasz szpilke....

Mazzop [ ]

Scatterhead - nie widzę jak informacja o X,XX i Y,YY miałaby dać wynik, nie wspominając, że każde zdjęcie zostanie policzone 2 razy

Scatterhead [ łapaj dzień ]

Mazzop -> zle sie wczytales, wynikiem bedzie X gdzie bedzie poczatek miejsca gdzie przecina sie najwiecej kwadratow na jednych wspolrzednych

master53 [ Senator ]

Scatterhead ->

oraz XX ktora zawiera informacje ile zdjec tam przetniesz maksymalnie

Ale skąd wzięło się XX ? Przecież właśnie szukaną jest maksymalna liczba przecięć.

eLJot [ a.k.a. księgowa ]

Scatterhead - Twój tekst jest jeszcze gorszy od tego z 1 postu :(

Raz: To nie są kwadraty!
Dwa: Twój "algorytm" sypnie się już w takim przypadku -->

Scatterhead [ łapaj dzień ]

elJot ->

"Twój "algorytm" sypnie się już w takim przypadku"

dla Y: da wynik 2 i miejsce przecieca na poczatku prostokata ponizej
dla X: da wynik 1 i miejsce przeciecia na lewym prostokacie

eLJot [ a.k.a. księgowa ]

Scatterhead
dla Y: da wynik 2 i miejsce przecieca na poczatku prostokata ponizej
dla X: da wynik 1 i miejsce przeciecia na lewym prostokacie

I jaki to ma związek z rozwiązaniem zadania?

Scatterhead [ łapaj dzień ]

może to posłużyć jako droga do wymyślenia rozwiązania

eLJot [ a.k.a. księgowa ]

Jakim cudem?

Spróbuj ten --->


W obu przypadkach rozwiązaniem jest 1, tylko nie wiem jak chcesz dojść do takiego wyniku.

GBreal.II [ floydian ]

Ja najpierw policzysz po x'ach a pozniej po igrekach, to rzeczywiscie, nie wywnioskujesz. Trzeba to robic inaczej.

Scatterhead [ łapaj dzień ]

Jak dodasz do odejmowania i dodawania +1 sprawdzanie czy kwadraty, ktorych wierzcholki sie przecinaja to rozwiaze sprawe? (nie sprawdzalem tego, tak tylko strzelam)

eLJot [ a.k.a. księgowa ]

Scatterhead - wiem, że jest późno, ale teraz to mnie zaczynasz denerwować.
To nie są kwadraty.
Zrozum wreszcie, że nie możesz rozdzielić rzędnych i odciętych współrzędnych wierzchołków, bo nigdy nie dowiesz, czy dane prostokąty maja wspólną część!

Scatterhead [ łapaj dzień ]

kwadraty, prostokaty wiadomo o co chodzi.

Zrozum wreszcie, że nie możesz rozdzielić rzędnych i odciętych współrzędnych wierzchołków, bo nigdy nie dowiesz, czy dane prostokąty maja wspólną część!

jezeli stworze takie tablice dla dwoch prostokatow

X:

P1: 0
P2: 4
K1: 5
K2: 6

Y:

P1: 0
K1: 4
P2: 5
K2: 7

i majac tablice elementow indeksowana numerami prostokatow, to w czym mi to przeszkadza zeby sprawdzic czy sie przecinaja?

Ramz [ Generaďż˝ ]

Scatterhead - sortowanie raczej odpada, bo najszybszym sposobem wyjdzie n(logn) a dla n =100000 to calkiem spory czas i do tego 2 takie listy :)

Tak sobie siadlem teraz i pomyslalem o jakims podziale docelowej tabicy(tej ze zdjecimi) na mniejsze kwadraty (czesci). Te czesci zawieraly by wskazniki na rzeczywiste zdjecia ktore znajda sie w danej czesi tablicy. nastepnie sprawdzamy punkt przeciecia sie tylko w danej czesci tablicy (co dosc znacznie zmniejszy ilosc porownan). Przy tym dochodzi brak sortowania, a wszystko robimy podczas wczytywania danych.

PS. Taki cos stosuje sie w grach, przy podzialach sceny np. do szybkiego liczenia kolizji (z tym ze tam sa stosowane rozne rodzaje drzew).

06.01.2008

17:14

[29]

master53 [ Senator ]

Już sam opracowałem wydajny algorytm, który to zlicza. Jakoś nie mogłem zrozumieć myśli ukrytej w waszych postach, ale i tak dziękuję za fatygę :)

Pozdrawiam.

06.01.2008

18:23

[30]

eLJot [ a.k.a. księgowa ]

master - pochwalisz się później?

06.01.2008

22:00

[31]

master53 [ Senator ]

eLJot -> Możemy pogadać po 7 stycznia ;)

Edit: Tak w skrócie sprawdzałem po kolei każdą współrzędną względem reszty jaka została. Przykładowo dla tego przykładowego wejścia:

-1 -1 1 2
0 -2 3 0
2 2 3 3
-1 -1 1 2
2 -1 4 1

Sprawdzałem -1 -1 1 2 z resztą współrzędnych, potem 0 -2 3 0 z resztą itd. Przy czym uwzględniłem przypadki gdzie większe zdjęcie, może być pokrywane przez mniejsze tak, że mniejsze nie wystaje poza obręb większego oraz gdy na sprawdzane zdjęcie nachodzą 2 zdjęcia, ale jednak nie pokrywają siebie tylko sprawdzane zdjęcie.

Edit2: Fajnie jeśli komuś by się chciało potestować mój program.