h3. Rezolvare:

În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul nostru de programatori . Vom folosi aceeaşi idee ce a apărut şi în celelalte probleme, adică numărăm pe rând în câte zone este împărţit planul de primele o dreaptă, doua drepte respectiv $n$ drepte. Deci vom adăuga în ordine dreptele la configuraţia noastră. Când adăugăm o dreaptă ea va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte, pe noi ne intereseaza punctele distincte, ca să facem acest lucru putem sorta punctele în $O(k log k)$ sau să folosim o tabelă de dispersie şi astfel să aflăm în $O(k)$ numărul de puncte distincte, daca acest număr e egal cu $L$ atunci la numărul curent de zone vom adăuga $L$ . Astfel algoritmul are complexitatea $O(n^2 log n)$ , sau dacă folosim tabele de dispersie $O(n^2)$ .

În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul nostru de programatori . Vom folosi aceeaşi idee ce a apărut şi în celelalte probleme, adică numărăm pe rând în câte zone este împărţit planul de primele o dreaptă, doua drepte respectiv $n$ drepte. Deci vom adăuga în ordine dreptele la configuraţia noastră. Când adăugăm o dreaptă ea va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte, pe noi ne intereseaza punctele distincte, ca să facem acest lucru putem sorta punctele în $O(k log k)$ sau să folosim o tabelă de dispersie şi astfel să aflăm în $O(k)$ numărul de puncte distincte, daca acest număr e egal cu $L$ atunci la numărul curent de zone vom adăuga $L$ . Astfel algoritmul are complexitatea $O(n{^2^} log n)$ , sau dacă folosim tabele de dispersie $O(n{^2^})$ .

h2(#problema-10). Problema 10 (["527 The partition of a cake":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=468]):