Wiele Kwadratów SPOJ

[teennewbie]

Witam,
jest sobie pewne zadanie na SPOJu

Posiadamy wielki, wręcz ogromny dywan z narysowanym na nim układem współrzędnych. Zostały na nim utworzone kwadraty pomalowane na biało i czerwono na wzór jaki przedstawiono niżej:

Na takiej planszy narysujemy prostokąt i musimy policzyć ile w tym prostokącie jest czerwonych kwadratów.

wzór/foto

AU

352hsv9.jpg (15.25 KiB) Przejrzano 171 razy

i mam pytanie bo np. w przykładzie powyzej mamy punkty
(1,4) i (8,8)
i czy jest jakiś 'sprytny' sposób aby to policzyc?

problem, jest nadal PRZEPRASZAM ZA DOUBLE POSTA

[mcbob]

Tak na pierwszy rzut oka. Bierzesz kolejne punkty należące do tego prostokąta typu \(\displaystyle{ (a,a)}\) gdzie \(\displaystyle{ a}\) naturalne, nieparzyste. Dla każdego takiego punktu sumujesz jego odległość od dolnej krawędzi prostokąta, od lewej krawędzi i dodajesz 1 (jako kwadracik o tych właśnie współrzędnych). Sumując to masz liczbę wszystkich kwadracików czerwonych w danym prostokącie. Nie widzę w tym nic trudnego wiec z zaklepaniem tego w jakimś języku programowania chyba sobie poradzisz. W twoim przykładzie takimi punktami byłyby \(\displaystyle{ (5,5)}\) i \(\displaystyle{ (7,7)}\)

[teennewbie]

trochę nie bardzo rozumiem, twojego toku rozumowania,
bo wg. Ciebie w nieparzystym wierszy kwadracików jest tylko jeden czerwony, a to nie zawsze.
no i w ogole twój sposob nie jest uniwersalny.

[Afish]

Liczbę czerwonych kwadracików w takim prostokącie (nazwijmy go P) możesz policzyć jako:
liczba czerwonych kwadracików w prostokącie, którego lewy dolny wierzchołek jest w punkcie (0,0), a prawy górny jest prawym górnym wierzchołkiem P - liczba czerwonych kwadracików w prostokącie, którego lewy dolny wierzchołek jest w punkcie (0,0), a prawy górny jest lewym górnym wierzchołkiem P - liczba czerwonych kwadracików w prostokącie, którego lewy dolny wierzchołek jest w punkcie (0,0), a prawy górny jest prawym dolnym wierzchołkiem P + liczba czerwonych kwadracików w prostokącie, którego lewy dolny wierzchołek jest w punkcie (0,0), a prawy górny jest lewym dolnym wierzchołkiem P. Ten wzór tylko brzmi skomplikowanie
Teraz pozostaje pytanie, jak obliczyć, ile jest kwadracików w prostokącie, którego lewym dolnym wierzchołkiem jest (0,0), a prawym górnym jakieś (a,b). A to można wyliczyć wykorzystując ten wzorek (nie gwarantuję poprawności):

Ukryta treść:    

\(\displaystyle{ \left \lfloor \frac{a}{2} \right \rfloor \cdot \left \lfloor \frac{b}{2} \right \rfloor + \sum_{i=1}^{\left \lfloor \frac{a}{2} \right \rfloor} min \left(i,\left \lceil \frac{b}{2} \right \rceil \right) + \sum_{i=1}^{\left \lfloor \frac{b}{2} \right \rfloor} min \left(i,\left \lceil \frac{a}{2} \right \rceil \right)}\)

[teennewbie]

a gdy prostokąt nie 'zaczyna sie' od wierzcholka (0,0) ?

[Afish]

Przeczytaj post dokładnie.

[teennewbie]

nadal mi się wydaję, że twoja odpowiedź jest błędna,
może źle napisałem zadnaie o to adres do zadania na SPOJ;u

[Afish]

Zgadzam się, miałem drobną literówkę w zapisie, ale już ją poprawiłem. Konkretniej zamiast podłogi miał być sufit, ale już jest ok.

[mcbob]

trochę nie bardzo rozumiem, twojego toku rozumowania,
bo wg. Ciebie w nieparzystym wierszy kwadracików jest tylko jeden czerwony, a to nie zawsze.
no i w ogole twój sposob nie jest uniwersalny.

Jest uniwersalny i jest poprawny. Po prostu nie zrozumiałeś tego co pisałem bo trzeba przyznać źle to wytłumaczyłem. Te kolejne punkty po których iterujesz w moim rozwiązaniu to są te punkty w których się zaginają czerwone paski wewnątrz podanego prostokąta. Ale tak jak zaznaczyłem to było takie rozwiązanie na szybko żeby tylko wyliczyć, poprawne ale nieoptymalne. Wykorzystując podany powyżej wzór masz rozwiązanie w czasie stałym.