algoritm envelope?

[•keenox]

Vreau sa fac o matrice 64000x64000 si nu vrea sa-mi compileze ca e prea mare. Am incercat si dinamic, dar programul este inchis de windows (vezi attachmentul). Dupa cum se vede am incercat sa maresc si stiva la 16mb, dar la fel. Ma poate ajuta cineva cu aceasta problema si eventual cu argumentele pt compilator?

[•svalentin]

Incearca sa folosesti STL bitset - http://www.sgi.com/tech/stl/bitset.html

Stiu ca desi bool ar trebui sa ocupe 1 bit, C-ul il tine ca 1 byte. Asta ar insemna 64k * 64k * 1 byte = 4GB.
Windows te lasa sa aloci maxim 2 giga bytes de memorie per proces. Incearca sa afisezi pe ecran i-ul din for. Asa o sa vezi exact cand iti da eraore programul si poti sa vezi cat ti-a intrat in memorie.

[•keenox]

i-am bagat "i"-ul pe output si se opreste la 33010. chestia cu bool-ul ca byte o stiam si mi se pare aiurea.

le: cum pot face o matrice din bitset? (adica de fapt un array). am incercat

Cod:

vector<bitset<MAX>> puncte(MAX);

dar nu merge.

[•Mishu91]

Cod:

#include <bitset>
using namespace std;
bitset<MAX> V[MAX];

L. E.
merge si

Cod:

vector <bitset<MAX> > V(MAX)

dar trebuie sa lasi spatiu intre cele doua semne de 'mai mare' de la vector si bitset pt ca '>>' inseamna deplasare pe biti

[•keenox]

mersi mult

[•svalentin]

i-am bagat "i"-ul pe output si se opreste la 33010. chestia cu bool-ul ca byte o stiam si mi se pare aiurea.

Observi? 64000 * 33010 * 1 byte ~= 2GB - acea limita maxima de memorie per proces.

[•keenox]

mersi pt raspunsuri. imi trebuia pt problema forum de la campion. imi poate explica si mie cineva de e ala algoritm envelope?  . ca la noi in "sat" n-are cine sa ne invete 

[•sigrid]

@keenox: Tonul de-l folosesti tu e unul urat. Nu e nimeni vinovat pentru destinul tau.

Si mie mi-ar placea sa stiu de unde pot invata despre algoritmul asta. Am incercat sa caut pe net, dar nu cred ca am dat peste ce trebuie  . Ma poate ajuta cineva, va rog?

[•keenox]

aseara eram nervos si aveam (inca am) motive sa fiu.

offtopic: nu exista destin. sau cel putin la modul la care te referi tu. dar sa lasam pb asta ca aici e forum de info, nu de filosofie

LE: m-am mai jucat un pic cu sursa programelului si cu bitseturile. am observat ca numai 2 declaratii de bitset imi consumau 0.750 s. e cam mult, enorm chiar, in situatia in care timpul maxim era de 0.35 pt problema. niste solutii mai rapide nu exista?

[•Adriana_S]

Mai interesant mi se pare ca in solutie, dupa ce se face Upper-Envelope si Lower-Envelope se parcurg toate anvelopele.

[•gabitzish1]

niste solutii mai rapide nu exista?

Diagrama Voronoi merge bine.

[•keenox]

la partea cu rapid, ma refeream la o alternativa mai rapida la bitset. cat despre solutia problemei nu comentez pentru ca, in primul rand, nu am inteles-o.

Adriana_S imi poti explica si mie, te rog, ce presupune algoritmul envelope? si ce sunt upper/lower-envelope? multumesc

[•Adriana_S]

Ma refeream la faptul ca envelope inseamna plic, nu anvelopa.
N-am nici o idee ce-s upper-envelope si lower-envelope, in mintea mea sunt partea de sus a plicului si partea de jos.

[•sima_cotizo]

Nu s-a gandit nimeni la o solutie cu mediatoare de segmente?  Mie in timpul rundei mi s-a parut ca functiona (ca iesea din timp era din vina mea, desi complexitatea era M log N)...

[•gabitzish1]

Eu am facut cu mediatoare de segmente... si a mers 

[•devilkind]

mediatoare de segmente? nu te referi cumva la voronoi?

[•gabitzish1]

Ba da, am construit poligonul asociat originii intersectand mediatoarele segmentelor (O,P_i).

[•sima_cotizo]

mediatoare de segmente? nu te referi cumva la voronoi?

Nu, nu am parcurs articolul cu voronoi cat sa-l si inteleg pe deplin
Luam toate segmentele pe care le facea O cu "casele" si le trasam mediatoarele (retineam a,b,c). Pt ca un centru sa fie valid, trebuia sa se afle de aceeasi parte a tuturor dreptelor ca si O (Gabriel, am considerat cazul in care mediatoarele nu se "inchid" intr-un poligon). Daca initial ordonam "casele" dupa panta lui OP_i, puteam sa caut binar doar 2 mediatoare cu care ar fi trebuit sa verific, cu restul fiind ok din start.

[•gabitzish1]

Eu am luat un poligon initial cu colturile in (32000, 32000), (32000, -32000), (-32000, -32000),  (-32000, 32000), si pe asta il intersectam cu fiecare mediatoare, la fiecare pas "aruncand" bucata de poligon care nu era de aceeasi parte cu O, astfel am obtinut de fiecare data un poligon, chiar daca nu era format in totalitate de mediatoare.
Query am facut in O(M*nr_laturi_poligon).

[•sima_cotizo]

Si eu m-am gandit la asta, dar era mai mult de munca. Daca ordonai punctele poligonului tau dupa panta lui OP_i, avand in vedere ca il contine pe O, puteai cauta binar si verificai in O(log nr_laturi) pe query. Ai luat 100?

PS: devenim off-topic... pana la urma ce e algoritmul upper/lower envelope?

[•gabitzish1]

Si eu m-am gandit la asta, dar era mai mult de munca. Daca ordonai punctele poligonului tau dupa panta lui OP_i, avand in vedere ca il contine pe O, puteai cauta binar si verificai in O(log nr_laturi) pe query. Ai luat 100?

PS: devenim off-topic... pana la urma ce e algoritmul upper/lower envelope?

Da, am luat 100 cu treaba aia.
On-topic... nu prea stiu ce e algoritmul upper/lower envelope...

[•gcosmin]

In solutia de la problema forum, autorul calculeaza mai pe lung niste drepte care impart planul in doua semiplane si ar trebui ca punctul nostru sa fie de aceesi parte a acestor drepte ca si punctul (0, 0), ca punctul sa fie bun (adica sa putem pune un forum acolo). Aceste drepte sunt de fapt, mediatoarele despre care vorbiti.

Daca intersectam aceste semiplane, o sa ne dea un poligon in interiorul caruia punctul de query trebuie sa se afle, ca sa fie bun. Ajungem deci la intersectii de semiplane, problema ce se poate rezolva in N log N.

Upper envelope si Lower envelope sunt urmatoarele chestii: impartim dreptele ce determina semiplanele in doua categorii (alea cu panta negativa si alea cu panta pozitiva). Daca intersectam semiplanele dintr-un tip o sa ne dea o structura ori convexa ori concava (un fel de semicerc superior si semicerc inferior (dar mai patratos : )). Astea se numesc upper envelope si lower envelope pentru ca parca impacheteaza ceva (cred.... nici eu nu stiu de ce le zice asa exact ). Acum punctul nostru trebuie sa fie sub upper envelope si deasupra lui lower envelope ca sa fie bun.

Pentru a determina unul din envelopuri, sortam dreptele dupa panta si iese un algoritm care se foloseste de o stiva. Parcurgem dreptele in ordine si tinem dreptele vizibile (din (0, 0) = origine) intr-o stiva. O dreapta nou bagata o sa faca cateva din ultimele drepte din stiva (posibil) sa nu mai fie vizible, si altfel le scoatem din stiva pe rand. La sfarsit in stiva se vor afla dreptele vizibile din (0, 0). Daca incercati acest algoritm cu toate dreptele odata o sa observati ca nu merge pentru se intampla dubiosenii cand treci la cealata multime de drepte.

Pentru a intelege mai bine algoritmul e bine sa desenati pe foaie cateva drepte de panta de acelasi semn si sa simulati putin, sa vedeti cum se comporta si de ce daca parcurgand dreptele in ordinea pantei, ultimele adaugate pot iesi.

Intersectia celor doua envelopuri ne da fix poligonul care reprezinta intersectia semiplanelor. Intersectia se poate rezolva in complexitate liniara si de aici complexitate de N log N pentru determinarea pligonului (N log N de la sortare).

Sper ca am fost destul de explicit si am lamurit pe toata lumea