h3. (problema medie, clasa a 9-a)
Mai intai sortam punctele crescator dupa abscisa, iar pentru abscise egale dupa ordonata. Acum, folosind cautarea binara putem cauta orice punct in timp logaritmic. Pentru fiecare pereche de puncte vom forma patratul care are o diagonala formata din perechea respectiva. Dupa ce calculam si celelalte 2 puncte, le cautam binar in vectorul sortat. Daca le gasim, inseamna ca am mai gasit un patrat. Complexitatea solutiei este $O(N^2^ log N)$. Precizia recomandata este de $10^-4^$.

Singura problema care ramane de rezolvat acum e calcularea punctelor patratului daca stim doar o diagonala. O metoda simpla de gasire a lor, ce nu necesita cunostiinte avansate de geometrie, este observarea simetriilor care se formeaza fata de centrul patratului. Fie $x0, y0$ si $x1, y1$ coordonatele diagonalei cunoscute iar $x2, y2$ si $x3, y3$ coordonatele necunoscute. Centrul patratului este mijlocul acestei laturi, cu coordonatele $mijx = (x0 + x1) / 2$ si $mijy = (y0 + y1) / 2$. Sa notam $dx = abs(mijx - x0)$ si $dy = abs(mijy - y0)$. Se observa ca daca $y0 < y1$ atunci $x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy$ iar $y3 = mijy + dx$. In caz contrar, avem $x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy$ iar $y3 = mijy + dx$.

Singura problema care ramane de rezolvat acum e calcularea punctelor patratului daca stim doar o diagonala. O metoda simpla de gasire a lor, ce nu necesita cunostiinte avansate de geometrie, este observarea simetriilor care se formeaza fata de centrul patratului. Fie $x0, y0$ si $x1, y1$ coordonatele diagonalei cunoscute iar $x2, y2$ si $x3, y3$ coordonatele necunoscute. Centrul patratului este mijlocul unei diagonale, deci coordonatele lui sunt $mijx = (x0 + x1) / 2$ si $mijy = (y0 + y1) / 2$. Sa notam $dx = abs(mijx - x0)$ si $dy = abs(mijy - y0)$. Se observa ca daca $y0 < y1$ atunci $x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy$ iar $y3 = mijy + dx$. In caz contrar, avem $x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy$ iar $y3 = mijy + dx$.

h2. Elimin