Solutia problemei Hidden Points

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 ≤ j < u (0 ≤ 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² * log(n)), e nevoie de query-uri pe numere reale pentru a diferentia intre dreptele candidat, deci nu obtine punctajul maxim.

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²*(log(X_MAX) + log(Y_MAX))).