h1(#hidden). 'Solutia':winter-challenge-2020/solutii/hidden problemei 'Hidden Points':problema/hidden_points

Solutia va fi postata in curand.

h2. Pentru $80$ de puncte:
 
Cautam binar, prin query-uri cu drepte verticale (orizontale), si gasim toate valorile $X{~j~}$ ({$Y{~k~}$}) pentru care exista macar un punct $i$ ascuns cu coordonata $X{~i~}$ ({$Y{~i~}$}) egala cu $X{~j~}$ ({$Y{~k~}$}). Sa zicem ca am obtinut $u$ ({$v$}) valori distincte de $X{~j~}$ ({$Y{~k~}$}), adica $0 &le; j < u$ ({$0 &le; k < v$}). Pana acum, am facut $O(n*(log(Y_MAX) + log(X_MAX)))$ query-uri.
 
Acum avem $u * v$ puncte _candidat_: Fiecare pereche $(j, k)$ ne spune ca $(X{~j~}, Y{~k~})$ poate fi unul din punctele ascunse. E clar ca punctele ascunse formeaza o submultime a punctelor _candidat_.
 
Sa ne alegem un unghi _random_ si sa trasam o dreapta $d$ la acel unghi, care trece, sa zicem, prin origine. Prin fiecare punct _candidat_ $P{~t~}$, ducem dreapta paralela cu $d$, pe care o notam cu $d{~t~}$. Sortam punctele _candidat_ dupa distanta intre $d$ si $d{~t~}$. Deoarece unghiul ales este _random_, este o sansa foarte mare ca dreptele consecutive (in ordinea sortarii) sa se afle la o distanta relevanta. In caz ca distanta intre doua drepte este mai mica decat $epsilon = 10^-6^$, alegem alt unghi.
 
Prin $O(n*log(n))$ query-uri cu drepte paralele cu $d$, putem determina precis care sunt acele $d{~t~}$ care contin punctele ascunse. Algoritmul poate fi implementat cu o functie recursiva care primeste intervalul $[st, dr)$ de indici ale dreptelor _candidat_, si apeleaza fiii $[st, (st + dr) / 2)$, $[(st + dr) / 2, dr)$ doar daca afla, prin query, ca exista macar un punct ascuns pentre candidatii de la $st$ la $dr-1$.
 
Desi, in practica, solutia este foarte eficienta ca numar de query-uri, iar complexitatea timp, data de sortarea _candidatilor_, este $O(n^2^ * log(n))$, e nevoie de query-uri pe numere reale pentru a diferentia intre dreptele candidat, deci nu obtine punctajul maxim.
 
h2. Pentru $100$ de puncte:
 
Putem să ne folosim de căutarea binară şi drepte verticale la query-uri pentru a găsi fiecare dreaptă verticală pe care se află puncte şi numărul acestora (folosim $O(n*log(X_MAX)$) query-uri). Acum pentru fiecare $X{~i~}$ trebuie să găsim unde se află fiecare punct. Putem să aplicăm o strategie similară şi să căutăm binar punctele astfel: Căutăm binar cel mai mic $Y$ care are un punct nedescoperit încă, iar la query folosim punctele $(X{~i~} + 1, 0)$ şi $(X{~i~}, Y)$. Astfel punctele din stânga dreptei ori au fost descoperite ori au abscisa egală cu $X{~i~}$ (acest pas foloseşte $O(n*log(Y_MAX))$ query-uri).
 
Raspunsul la query nu trebuie decat comparat cu numarul de puncte cunoscute deja care se afla sub dreapta. E suficient sa verificam, intr-o maniera brute-force, care dintre punctele cunoscute se afla sub dreapta. Complexitatea ca timp este $O(n^2^*(log(X_MAX) + log(Y_MAX)))$.