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 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 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 $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ă.