[C]Test na sprawdzenie samego siebie :))

[lol_niezly]

Myslisz ze wymiatasz w C ??? :D
Ja tez tak myslalem dopoki nie natknalem sie na to:

main() { printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);}

Pytanie jest ( bez uruchamiania programu !!! )
- co to cos robi :)

A jak go uruchomicie, to JAK to robi i dlaczego ;0
Powiem szczerze, ze hhehe :D nie wiem :P

[alsor]

Niezdefiniowane: 'unix'
tak wspaniale to działa.

jakiś przedpotopowy konsolwy szmelc.

[lol_niezly]

Oj stary, wylozyles sie na poczatku :))
Tu wszystko jest dobrze, nawet jednego warninga nie dostaniesz :)
Program korzysta chyba ze wszystkich mozliwych sztuczek na wskaznikach i hasa po
pamieci i iscie mistrzowski sposob.

PS. to nie jest przedpotopowy konsolowy szmelc, ale najlepszy jak do tej pory
jednolinijkowy program z pewnego konkursu :) - program jest z `87
W tym przykladzie Unix jest zdefiniowane i ma wartosc 1 :)
Wlasnie o to chodzi zeby rozgryzc jak to dziala :d

[lol_niezly]

no ewentualnie mozesz dodac #include <stdio.h> ;)

[ktosktomafajnegomisiaczka]

przynam, bez odpalania dluzsza chwile zajmuje analiza programu, ale sie da:)
<br/>
<br/>
printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);<br/>
<br/>
po pierwsze, bardzo tutaj wazne jest, ze:<br/>
(indeks)["napis"] == "napis"[indeks]<br/>
z racji tego, ze oba sa tlumaczone na odczyt z adresu (adres"napis"u + index)
<br/><br/>
sprawa druga: <br/>
unix == 1, a wiec:<br/>
&unix["\021%six\012\0"] == &((1)["\021%six\012\0"]) == &("\021%six\012\0"[1])
== "%six\012\0"<br/>
(unix)["have"] == (1)["have"] == "have"[1] == 'a'<br/>
<br/>
stad, program wyglada w rzeczywistosci tak:<br/>
printf("%six\012\0",'a'+"fun"-0x60);<br/>
<br/>
idac dalej: \012 to oktalny zapis znaku 0x0A czyli.. nowej linii. \0 to koniec
ciagu znakow, tutaj niepotrzebny, poniewaz string sam zawsze jest takowym
konczony!<br/>
program jest rownoznaczny z:<br/>
printf("%six\n",'a'+"fun"-0x60);<br/>
<br/>
ostatnia sprawa, co to kurcze jest 'a' + "fun" - 0x60 :)<br/>
wlasciwie.. to to banal.. 'a' to 0x61<br/>
'a'+"fun"-0x60 daje "fun"+0x61-0x60 czyli.. "fun"+1.<br/>
printf traktuje to jako adres stringa do wstawienia za %s, <br/>
a wiec "widzi" adres stringa "un"!<br/>
stad.. program sie redukuje do:<br/>
printf("%six\n","un");<br/>
dalej juz zostawie bez komentarza.. :)

[ktosktomafajnegomisiaczka]

to forum tlumaczy tagi:( sorry wielkie za maloczytelny tekst.. tutaj poprawka:

przynam, bez odpalania dluzsza chwile zajmuje analiza programu, ale sie da:)


printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);


po pierwsze, bardzo tutaj wazne jest, ze:
(indeks)["napis"] == "napis"[indeks]
(z racji tego, ze oba sa tlumaczone na odczyt z adresu (adres_tekstu_napis +
index))

sprawa druga:
unix == 1, a wiec:
&unix["\021%six\012\0"] ==
&((1)["\021%six\012\0"]) ==
&("\021%six\012\0"[1]) ==
"%six\012\0"
i:
(unix)["have"] ==
(1)["have"] ==
"have"[1] ==
'a'

stad, program wyglada w rzeczywistosci tak:
printf("%six\012\0",'a'+"fun"-0x60);

idac dalej:
\012 to oktalny zapis znaku 0x0A czyli.. nowej linii (=='\n')
\0 to koniec ciagu znakow, tutaj niepotrzebny, poniewaz string
zawsze nim konczony!

czyli, program jest rownoznaczny z:
printf("%six\n",'a'+"fun"-0x60);

ostatnia sprawa, co to kurcze jest 'a' + "fun" - 0x60 :)
wlasciwie.. to to banal..
'a' == 0x61
wiec:
'a'+"fun"-0x60 ==
"fun"+0x61-0x60 ==
"fun"+1 ==
"un"

a wiec printf "widzi" stringa "un"..
stad program sie redukuje do:
printf("%six\n","un");

dalej juz zostawie bez komentarza.. :)

[alsor]

Chyba sam się wyłożyłeś, nie wpisując pełnego kodu tego szmelcu.
To ma być program!

Jeżeli takimi bezużytecznymi szmatami zajmują się na tych konkursach, to jestem
bardzo szczęśliwy, że nigdy mnie to nie rajcowało.

A jeśli lubisz analizować takie tam, to weź sobie otwórz w notatniku dowolny
plik exe i zbadaj co on robi - ŁUHAHAAŁAAAAAA HA HA!

Można też badać 'pismo' egipskie lub napisy w jaskiniach...

[ktosktomafajnegomisiaczka]

analiza exekow w notepadzie nie jest az taka bezsensowna rzecz jak Ci sie
wydaje.. mozna znalezc tam czesto bardzo ciekawe informacje :)

natomiast kod ktory kolega podeslal jest kompletny.
wszystko zalezy od kompilatora ktorego uzywaz.
jesli nie masz wlaczonej opcji auto-dolaczania standardowych bibliotek, to
rzeczywiscie "brakuje" linijki na poczatku "#include <stdio.h>" ktora
zdefiniuje funkcje printf() oraz stala UNIX.
aczkolwiek powtarzam, zalezy od ustawien kompilatora

uprzedzajac pytania - nie, nie przylepie sobie "aczkolwiek" na lodowke :)

[alsor]

Nie wiem czym i gdzie to kompilujecie - nie ma żadnego 'unix' w stdio.h

[ktosktomafajnegomisiaczka]

#define UNIX 1

znajduje sie w prawie kazdym naglowku bibliotek na linuxie..

[alsor]

Znasz algorytm na pole figury o danych wierzchołkach?

struct Point { int x, y; }

Mamy te wierzchołki w tablicy:
Point *t;
int n = liczba punktów w t;


t[0] = t[n-1] - 'polygon' zamknięty

Dla wielokąta, którego boki nie przecinają się (bez dziur) pole łatwo obliczyć:
pole = suma dx*(y1+y2)/2;
ale gdy są dziury (np. gwiazda) to tak nie można.

[ktosktomafajnegomisiaczka]

rozumiem ze w tym wzorze masz sume po kelejnych punktach, dx = x2-x1, x1y1 to
punkt 'aktualny', a x2y2 - 'natepny'?
troszke Cie zmartwe - to nie tak.. ten wzor to zywcem wzieta calka z 'linii
lamanej' ale.. liczaca pole miedzy ta linia a osia OX. to w zaden sposob nie
policzy Ci Pola np. trojkata (0,0),(1,10),(5,5).

ogolnie, kazda figure mozna rozbic na 'linie lamane' (np. najprosicej linie
rysujaca 'gorna granice figury' i 'dolna granice', polaczone koncami daja
figure). dla kazdej takiej 'linii lamanej' mozna przy pomocy tego wzoru co
podales obliczyc pole pod ta linia (tzn. miedzy ta linia a osia OX). teraz, w
zaleznosci od tego jak dokladnie te linie sa ulozone w przestrzeni, wystarczy
pododawac lub poodejmowac je odpowiednio miedzy soba (co dokladnie - zalezy jak
podzieliles figure na linie.. w przypadku podzialu liniagorna/liniadolna
wystarczy odjac).
figura z zaznaczonymi wierzcholkami wyraznie:
_____________
____X___X____
___/_\_/_\___
__/___X___\__
_X_________X_
__\___X___/__
___\_/_\_/___
____X___X____
_____________
(ciekawe czy obrazek sie skopie.. jak tak, wklej go do notatnika)
figura wyglada tak (wierzcholki nie maja szerokosci ani wysokosci!!):
__________
___/\/\___
__/____\__
__\____/__
___\/\/___
__________

lewy-dolny rog obrazka to 0,0.
wierzcholki figury to: (4,1),(5,2),(6,1),(8,3),(6,5),(5,4),(4,5),(2,3),(4,1)
'linia gorna' figury: (2,3),(4,5),(5,4),(6,5),(8,3)
'linia dolna' figury: (2,3),(4,1),(5,2),(6,1),(8,3)

pole pod gorna:
2*4 + 1*4,5 + 1*4,5 + 2*4 = 25kratek kwadratowych
pole pod dolna:
2*2 + 1*1,5 + 1*1,5 + 2*2 = 11kratek kw.
czyli pole figury to:
25-11 = 14kratek kw.

liczac z rysunku -
8 pelnych kratek, pole pelnej wartosci => 8
12 lini ukosnych, pole=polowa kratki => 6
razem = 14kratek kw.

sposob zawsze dziala, jest to dokaldne przeniesienie matematycznej metody
obliczania powierzchni figur. niestety.. czesto trudno jest napisac kawalek
kodu ktory dokladnie podzieli nam figure na 'linie gorna' i 'linie dolna',
zwlaszcza gdy na przyklad figura sama sie przecina ze soba - np. narysuj figure:
(0,0)->(4,4)->(0,4)->(4,0)->(0,0)
widac od razu, ze tylko i wylacznie operujac na zbiorze punktow ktory rysujesz
nie da sie okreslic 'linii gornej' i 'linii dolnej' bo.. rysujacy sprytnie
pozbyl sie punktu (2,2). algorytm ktory by okreslal linie gorne i dolne figur,
musialby zauwazac ze linie figury sie przecinaja, i dodawac ten punkt do zbioru
rysujacego figure. ale to juz inna bajka :)

[lol_niezly]

Ktostomafajnegomisiaczka :

Stary, jak dlugo siedzisz w tej brazny :)?? i gdzie studiujesz, bo wymiatasz :D

[ktosktomafajnegomisiaczka]

konkretnie jak znam C/C++ to bedzie z ladnych pare lat :) hm. ze siedem albo
osiem kurcze juz.. a siedze sobie na Informatyce Wydzialu ETI Politechniki
Gdanskiej :)

[alsor]

>troszke Cie zmartwe - to nie tak.. ten wzor to zywcem wzieta calka z 'linii
>lamanej' ale.. liczaca pole miedzy ta linia a osia OX. to w zaden sposob nie
>policzy Ci Pola np. trojkata (0,0),(1,10),(5,5).

wg wzoru tej 'zwykłej całki' można obliczyć pole dowolnego wielokąta bez
przecinających się krawędzi (i leżącego w całości po jednej stronie osi x, ale
to nie jest problemem - zawsze można to przesunąć... a może wystarczy mała
korekta wzoru: (x2-x1)*(|y1|+|y2|) -> nie sprawdzałem tego).

Ten trójkąt:
(0,0),(1,10),(5,5) i (0,0) -> zamykamy.
2s = |(1-0)(10+0) + (5-1)(10+5) + (0-5)(0+5)| = |10 + 60 - 25| = 45

licząc pole trójkąta z wyznacznika: 2s = moduł z
0 0 1
1 10 1
5 5 1
= |5 - 50| = 45, czyli jest ok

----------
teraz ta figura:
(4,1),(5,2),(6,1),(8,3),(6,5),(5,4),(4,5),(2,3),(4,1)
sum = 1*3 + 1*3 + 2*4 - 2*8 - 1*9 - 1*9 - 2*8 + 2*4 =
3 + 3 + 8 - 16 - 9 - 9 - 16 + 8 = -28
czyli: s = |sum|/2 = 14


Ale chodzi mi o dowolną figurę - podziurawioną, posiekaną i przenikającą się
dowolnie z samą sobą... taki można narysować funkcją polygon.

Punkt P należy do wnętrza, takiego dowolnego, wielokąta wtedy, gdy prosta
poprowadzona z P do nieskończoności przecina nieparzystą liczbę jego krawędzi.

Chyba wzór Greena: całka po konturze = całka po powierzchni...
ale trzeba jeszcze uwzględnić zmiany kierunku cyrkulacji, albo wszystkie
przejścia kąta przez 2pi lub coś tam...

[ktosktomafajnegomisiaczka]

oj, nie no, przepraszam, nie sprawdzalem czy to dziala - poprostu wygladalo mi
na przyblizenie calki trapezami :)

|Y|-|Y| pewnie nie zadziala, bo skro to nei calka :) to ten wzor musi raczej
jakos z przyrostow lub gradientow sie wywodzic, a takie zabsowanie wydaje mi
sie ze by je rozwalilo calkiem przy przejsciu przez os OX.. szcerze mowiac, nie
korzystalem z tego wzoru i nie wiem, trzeba poeksperymentowac :) najprosciej
rzeczywiscie przesunac figure tak zeby cala byla ponad OX.

co do przecinania sie krawedzi to wlasnie tez pisalem na samym koncu, ze jak
figura ma takowe przeciecia, to trzeba je najpierw odnalezc i update'owac zbior
wierzcholkow rysujacych.. i to generalnie by wystarczylo dla dowolnej figury,
zwlaszcza ze po znalezieniu przeciec mozna figure rozbic na pod figury i wtedy
juz sobie dowolnie ich poa obliczyc.. - problem tylko z narastajaca liczba
wierzcholkow ktore trzeba sobei poodnajdywac i podopisywac - trzeba by przeciez
kazda krawedz z kazda sprawdzac czy aby przeciecia nie ma :( [tak potem chwile
pomyslalem ile to trzebaby sie narobic z wytyczaniem wlaciwego konturu, jak
jedna krawedz przetnie cztery inne..]

co do calki po konturze/powierzchni to nie jestem pewien o czym, mowisz,
przyznam jesli by tak zcalkowac po powierzchni figury funkcje f(x,y)=1 to
rzeczywiscie dostanie sie objetosc rowna co do wartosci powierzchni tej
figury :) aale.. jak z kolei opisac figure funkcja dajaca sie tak zcalkowac -
nie wiem..

hm ;) ciekawy problem, mam nadzieje ze matematycy juz maja jakis na to algorytm
gotowy :] zawsze jesze zostaje narysowanie tej figury z przykazanym
wypelnieniem roznym od koloru tla, potem preskanowanie bitmapy obrazu i zliceni
pixeli odpowiadajacych temu kolorowi.. rozwiazanie chamskie, ale zadziala na
pewno ;)

[alsor]

> co do calki po konturze/powierzchni to nie jestem pewien o czym, mowisz,
> przyznam jesli by tak zcalkowac po powierzchni figury funkcje f(x,y)=1 to
> rzeczywiscie dostanie sie objetosc rowna co do wartosci powierzchni tej
> figury :) aale.. jak z kolei opisac figure funkcja dajaca sie tak zcalkowac -
> nie wiem..

Jeden z wzorów Greena:
Ic(Pdx + Qdy) = Is(Qx - Py)ds; gdzie: Qx = dQ/dx, Py = dP/dy
Ic - całka po zamkniętym konturze,
Is - całka po powierzchni zawartej w tym konturze.

Teraz wystarczy, aby: |Qx - Py| = 1 -> wtedy otrzemamy powierzchnię

Przyjmę sobie: Qx = 0 i Py = 1, czyli: P = y
mamy całkę: Ic(ydx)
kontur to odcinki:
(x,y) = (x1,y1) + t(x2-x1, y2-y1), postać parametryczna - t<0,1>

Ic(ydx) = It(y1 + t(y2-y1))(x2-x1)dt = y1(x2-x1)t + (y2-y1)(x2-x1)t^2/2
wstawiając granice: y1(x2-x1) + (y2-y1)(x2-x1)/2 = (x2-x1)(y2 + y1)/2
dla kolejnych odcinków - podobnie...

Jest to ten wzór, który podałem na początku - nawet nie trzeba nic przesuwać...

---------
Przyjmując: Qx = 1/2 i Py = -1/2, otrzymamy inny wzór: x1*y2 - x2*y1

Ale to nie załatwia problemu dziur...

[ktosktomafajnegomisiaczka]

jakich dziur? masz na mysli np. okrag R=20m i w wspolsrodkowy otworek R=5m?

ale czegos takiego chyba sie nie da narysowac pojedyncza funkcja rysujaca
poligon na podstawie wierzcholkow..?

[alsor]

> jakich dziur? masz na mysli np. okrag R=20m i w wspolsrodkowy otworek R=5m?
>
> ale czegos takiego chyba sie nie da narysowac pojedyncza funkcja rysujaca
> poligon na podstawie wierzcholkow..?

Da się takie coś narysować (jednym ciągiem łamanych):
- najpierw robisz koło zewnętrzne R = 20 (taki wielokąt foremny z krótkich odcinków)
- teraz odcinek do środka - długości 15
- dalej, koło wewnętrzne R = 5
- ostatni odcinek na koło zew. - powrót do punktu początkowego i zamknięcie łamanej.

[alsor]

tylko, że taki pierścień nie ma przecinających się krawędzi,
są tu dwie pokrywające się, ale to nie przeszkadza.

Taka 'prawdziwa dziura' występuje gdy krawędzie się przecinają, np. gwiazda
pięcioramienna (7, 9, ...) narysowana 'jednym ciągiem'.

[ktosktomafajnegomisiaczka]

[metody czysto matematyczno-geometrycznej caly czas nie widzialem..]

mmm.. taka implementacja poligon'a.. myslalem o takie co poprostu rysuje kontur
i go wypelnia wewnatrz calkiem, nie taka co wypelnia na przemian w momencie
przeciecia krawedzi. w takim razie w takim razie.. co bys powiedzial jednak na
wyszukanie przeciec, zbudowanie grafu reprezentujacego figure, puszczenie
algo "pokolorowania" grafu dwoma kolorami z regulami zgodnymi z dzialaniem
poligon() i posumowanie pol (na pewno nie dziurawych bo znalezlismy wszystkie
przeciecia) podfigur wlasnie "pokolorowanych" kolorem wypelnienia? :) inaczej
zostaje rzeczywiscie symulacja rysowania i badanie kierunku rysowania i
updateowanie aktualnego stanu 'rysunku' w momencie wykrycia przeciecia..