Ako pretpostavimo da se kvadrati ne poklapaju, i ako dva kvadrata nemaju jednaku x koordinatu gornjeg desnog ugla, pokusaj ovako:
Potrebno je da odredis ukupnu povrsinu svih kvadrata T. To ces utvrditi prostim zbirom povrsina svih kvadrata.
Doprinos svakog kvadrata sa sa pocetnom koordinatom x=x0 i stranicom a, prikazan na slici crnom linijom,
koja u rastucem strmom delu ima koeficijent k=a mozemo predstaviti zbirom dve funkcije, kao na slici.
Znaci, napravis skup uredjenih parova, pri cemu svaki kvadrat ucestvuje sa dva uredjena para (x0,a) i (x0+a,-a). Prvi elemenat odgovara x koordinati koja definise pocetak poluprave (x0,0), a drugi odgovara koeficijentu poluprave. Ovaj skup sortiras neopadajuce po prvom elementu uredjenog para. Ako su prvi elementi uredjenih parova jednaki doci ce do problema, i ovaj postupak se ne moze primeniti.
Neka P bude povrsina do sada dodatih kvadrata. Za pocetak P=0. Neka X bude trenutna pozicija prave koja treba da deli povrsine kvadrata na T/3. Za pocetak X = x0[i=0] kvadrata koji je prvi sa leve strane (prvi element prvog uredjenog para nakon sortiranja). Neka K bude koeficijent prave na kojoj lezi duz koja spaja trenutnu i proslu kriticnu tacku. Za pocetak, K = 0.
Princip rada:
Prelaskom na sledecu kriticnu tacku X = (x0[i=1])(sledeci uredjen par po sortiranom redu) korigujes vrednost za K, dodavanjem a prosle kriticne tacke a[i=0], tj. K = 0 + a[0]. Na P dodajes prirastaj koji nastaje, tj, P2 = P; P = P + (x0[1]-x0[0]) * K. Ako P prevazilazi T/3, linearnom interpolacijom na osnovu prosle vrednosti za P, tj. P2, P, i (x0[1]-x0[0]) moze se utvrditi tacna vrednost za X. Ako P nije jos doseglo T/3, proracunavanje nastavljas dalje. Dalje posmatras tacku X = (x0[i=2]), itd... analogno vec opisanom postupku. -> K = K + a[1]; P2 = P; P = P + (x0[2]-x0[1]) * K. ...
Mozda se negde krije greska, ne mogu sad na brzinu da je primetim. Hope I helped you a bit. :)
Za univerzalnije resenje koje ne zahteva postovanje uslova iz prve recenice posta se pomuci sam.
Edit: Ako pre sortiranja sve uredjene parove sa istim prvim elementom zamenis jednim uredjenim parom, po principu (x0,a0), (x0,a1), (x0,a2)...,(x0,an) -> (x0,a0+a1+a2+...an), jedini uslov koji ogranicava upotrebljivost navedenog postupka je da se kvadrati ne preklapaju.
O_o
ideja potrebna :) 15chars
