Dualizarea este un concept folosit în geometrie prin care putem să transformăm un punct într-o dreaptă şi invers astfel încât oricărei teoreme din planul primal îi corespunde o teoremă din planul dual. Pentru mai multe detalii vă recomand următoarele linkuri: {"wikipedia":https://en.wikipedia.org/wiki/Duality_(projective_geometry)} , "Point‐Line Duality":https://www.cs.tulane.edu/~carola/teaching/cmps6640/spring16/slides/Point-Line%20Duality.pdf

O proprietate a spaţiului dual este că dacă în plan primal un punct $A$ se află sub dreapta $d$ atunci în plan dual punctul $D$ se află sub dreapta a ($D$ este punctul obţinut din dreapta $d$, iar a este dreapta obţinută din punctul $A$)

O proprietate a spaţiului dual este că dacă în plan primal un punct $A$ se află sub dreapta $d$ atunci în plan dual punctul $D$ se află sub dreapta a ({$D$} este punctul obţinut din dreapta $d$, iar a este dreapta obţinută din punctul $A$)

h3. Demonstraţie:

h2. Pentru $100$ de puncte:

Pentru a obţine punctaj maxim avem nevoie de o structură de date care să gestioneze în mod eficient punctele. Putem să folosim un Quad-Tree care la fiecare pas împarte planul în 4 cadrane cu număr aproximativ egal de puncte. În fiecare nod reţinem câte puncte se află în cadranul corespunzător. Complexitatea pentru construcţia arborelui este $O(n * log(n))$ dacă la fiecare pas este împărţit doar cel mai mic dreptunghi care conţine punctele din nodul actual. Pentru query observăm că o dreaptă nu poate să taie mai mult de 3 cadrane deci la fiecare pas putem să eliminăm cel puţin unul dintre acestea şi să mergem recursiv în cadranele care nu se află complet sub dreaptă. Complexitatea acestui query respectă formula $T(n) = 3 * (T(n / 4)) + O(1)$ deoarece merg recursiv în maxim 3 cadrane care au aproximativ $n / 4$ puncte, deci, din {"Master Theoreme":https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}, $T(n) = O(n^log{~4~}3^)$. Complexitatea finală este $O(n * log(n) + q * n^log{~4~}3^)$.

Pentru a obţine punctaj maxim avem nevoie de o structură de date care să gestioneze în mod eficient punctele. Putem să folosim un Quad-Tree care la fiecare pas împarte planul în 4 cadrane cu număr aproximativ egal de puncte. În fiecare nod reţinem câte puncte se află în cadranul corespunzător. Complexitatea pentru construcţia arborelui este $O(n * log(n))$ dacă la fiecare pas este împărţit doar cel mai mic dreptunghi care conţine punctele din nodul actual. Pentru query observăm că o dreaptă nu poate să taie mai mult de 3 cadrane deci la fiecare pas putem să eliminăm cel puţin unul dintre acestea şi să mergem recursiv în cadranele care nu se află complet sub dreaptă. Complexitatea acestui query respectă formula $T(n) = 3 * (T(n / 4)) + O(1)$ deoarece merg recursiv în maxim 3 cadrane care au aproximativ $n / 4$ puncte, deci, din {"Master Theorem":https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}, $T(n) = O(n^log{~4~}3^)$. Complexitatea finală este $O(n * log(n) + q * n^log{~4~}3^)$.

Pentru $100$ de puncte trebuie să mai facem o optimizare. Putem să generăm răspunsurile pentru fiecare query în plan dual. Astfel în Quad-Tree vom pune punctele de query şi pentru fiecare dreaptă o să facem lazy update pe cadranele complet aflate sub dreaptă. La final trebuie decât să mai parcurgem o dată arborele pentru a extrage răspunsul pentru fiecare query. Astfel complexitatea finală devine $O(n * log(n) + n * q^log{~4~}3^)$. Deşi complexitatea teoretica pare că este destul de mare, acest algoritm se comportă foarte bine în practică.