h3. (problema grea, clasele 11-12)

Vom considera semidreptele ce pleaca din origine si trec printr-un capat al unui segment. Vor exista $2*N$ astfel de semidrepte. Pentru fiecare din cele $2*N$ unghiuri formate consideram bisectoarea sa. Orice alta semidreapta ce pleaca din origine va intersecta aceleasi segmente cu una din cele $2*N$ bisectoare. Deci Gigel nu trebuie sa traga decat in unele din aceste bisectoare. In loc de bisectoare se putea considera orice alta semidreapta strict in interiorul unghiului, dar bisectoarea este mai usor de calculat.
 
Vom forma un sistem cu $N$ ecuatii si $2*N$ necunoscute astfel: pentru un segment $i$ se formeaza o ecuatie de forma
 
* $B{~i~} = X{~1~} * A{~i,1~} + X{~2~} * A{~i,2~} + ... + X{~2*N~} * A{~i,2*N~}$
** $B{~i~}$ este starea initiala a neonului $i$
** $X{~1~}, X{~2~}, ..., X{~2*N~}$ sunt cele $2*N$ necunoscute care semnifica faptul ca se trage pe directia respectivei bisectoare
** $A{~i,j~} = 1$ in caz ca bisectoarea $j$ intersecteaza segmentul {$i$}, $0$ in caz contrar.
Sistemul se va rezolva modulo $2$ folosind metoda lui Gauss.
 
Pentru calcularea valorilor $A{~i,j~}$ se calculeaza unghiul format de semidreptele ce trec prin capetele segmentului $j$ si se testeaza daca semidreapta i se afla in interiorul sau. Trebuie avut grija la eventualele cazuri care apar, in special cand unghiul are o semidreapta in cadranul $4$ si alta in cadranul {$1$}.
 
Complexitate $O(n^3^)$
 

==Include(page="template/preoni-2007/footer")==