Nisi precizirao ogranicenje za N (gornje, naravno), pa ne znam da li ce algoritam koji ti predlazem biti dovoljno efikasan... Svodi se na to da ravan izdelis na vertikalne "strafte" pravama koje sadrze vertikalne stranice svih kvadrata, sortiras sve te strafte (po x koordinatama) i onda krenes sa leva na desno sabirajuci povrsine u svakoj strafti dok ne stignes do 1/3 i 2/3 ukupne povrsine.

Ovo je samo otprilike i na brzinu pa zahteva i malo truda sa tvoje strane.

Hev fan,
D.

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.

>
>
Hvala vam!
Ovu prvu ideju sam i ja pokusao, ali je bila prespora (verovatno lose
odradjen alg), a ovo drugo je interesantno.
Jos jednom vam se zahvaljujem na brzim i korisnim odgovorima.
Poz,
BIG FOOT