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 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. Avand maxim $2*N$ bisectoare ne vom incadra in limitarea de $10.000$ de trageri.

Vom forma un sistem cu $N$ ecuatii si $2*N$ necunoscute astfel: pentru un segment $i$ se formeaza o ecuatie de forma

Complexitate $O(n^3^)$

O optimizare, care insa nu era necesara pentru obtinerea punctajului maxim, ar fi reprezentarea sistemului format pe biti reducand complexitatea la {$O(n^3^ / log n)$}.
 

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