239 Points

[•Cosmin]

Aici puteţi discuta despre problema Points.

[•gogu]

Cam ce complexitate ati scos aici?
Eu am facut in O(N+2^(D*3)), cu D=numarul de dimensiuni dar cineva mi-a zis ca s-ar putea face in O(N log N) si eu nu-mi dau seama cum.

[•PuMa]

Ce e special la ultimele la 6 teste de tot nu pot sa le trec??? Complexitatea mea e tot O(N + 2 ^ (D * 3)).

[u-92]

poate nu folosesti long long

[•PuMa]

Folosesc!   Nush ce poate avea

[andreit1]

Pune long long si la numerele pe care le inmultesti( daca faci undeva inmultiri) nu doar la rezultat. Calculele pot sari peste... Si eu tot 70 am luat din cauza asta initial...

[•PuMa]

ms, de la asta era. pusesem niste long long-uri da nu pusesem peste tot.

[•alexthero]

Eu am scos O(n)

[•Cosmin]

Asa au scos toti ...

[•cos_min]

Cum ati facut de ati scos O(n)?  dak poate cineva sa imi explice plz plz 

[•filipb]

Aria unui triunghi de varfuri A(x1, y1), B(x2, y2), C(x3, y3) este:
|(x3-x1) * (y2-y1) - (x2-x1) * (y3-y1)| / 2 . De aici devine evident, pentru ca expresia din modul trebuie sa fie numar par ca aria sa fie numar natural. Si asta se poate face simplu in O(N) daca preprocesezi informatii de genul:
M[r1][r2] = numarul de puncte (x,y) din cele N care au x % 2 = r1 si y % 2 = r2, r1, r2 din {0,1}. Si vezi cum trebuie sa aduni ( ai grija si sa nu numeri acelasi triunghi de mai multe ori, pt. ca de exemplu ABC este acelasi lucru cu ACB, BCA, etc )... Spor