217 Popandai2

[ditzone]

Aici puteţi discuta despre problema Popandai2.

[•unholyfrozen]

Am si eu o intrebare legata de modul in care au fost concepute testele.  Cum generezi un poligon convex de N puncte? Daca generezi aleator cat de multe puncte vrei si faci infasuratoarea convexa sunt prea mici sansele sa aiba 1000 puncte.

[•Cosmin]

Poti genera vectori aleatori care sa aiba suma (0,0) si vectorii astia sa ii sortezi dupa panta si apoi astia pusi cap la cap formeaza un poligon convex ...
[edit] daca generezi aleator n puncte si faci infasuratoarea convexa, atunci pe infasuratoare vor fi O(log n) puncte

[•svalentin]

Interesanta ideea ideea de generare a poligonului convex!
Thx for sharing!

[•svalentin]

Pentru cei care primesc incorect pe ultimul test, un hint: mi se pare ca exista 3 puncte coliniare!

[•lucicanu]

Cum pot rezolva problema asta fara 4 for-uri?
Alta metoda nu stiu, poate cineva sa-mi dea cel putin un indiciu?

[•alexthero]

Incearca ca pt fiecare diagonala posibila sa gasesti cel mai mare patrulater

[•lucicanu]

Pai asta am facut pana acum: 2 for-uri pt diagonala+2 for-uri pt celelalte 2 puncte.
Fii putin mai concret: cum scap de for-uri? pls...

[•alexthero]

Cu binary search iei 70-90 de puncte. Dupa aceea poti observa ca punctele cautate sunt foarte apropiate de punctele gasite anterior (pentru cazurile mari) si poti optimiza un pic, iese O(n^2).

[•MarcvsHdr]

Ceva e ciudat cu evaluatorul la problema asta. Primesc 70p, dar nu imi spune ce e gresit. Cand dau pe Borderoul de Evaluare scrie:
"Compilare: "
si mai jos se buseste pagina... adica se vad butoanele aiurea si fondul albastru si... in fine, a mess. Doar la problema asta. Ma intriga la culme, ca desi suspectez WA, sunt tare curios ce s-a intamplat cu alea 3 teste.

[•bogdan2412]

Looks fine to me in firefox, konqueror. sunt wauri

[•MarcvsHdr]

Am observat si eu, sorry, my fault. 
Mi s-a busit Mozilla si l-am reinstalat.

[•devilkind]

ceva special pe primu test?? iau WA restu OK

[•CezarMocan]

Cam ce optimizari s-ar putea face pentru 100?

[•Cosmin]

E articol cu solutii, l-ai citit?

[•CezarMocan]

Nu... nu-l gasesc  . Imi dai te rog link?

[•savim]

Apropo, problema merge si O (N ^ 2 log N) cu O (n ^ 2) luam doar 70, poate te ajuta...

[•Mishu91]

Imi puteti da un hint cu sa fac in O(N^2), adica dupa ce am ales 2 puncte, nu prea imi iese cum as putea determina celelalte 2 in O(1) 

[•CezarMocan]

Andrei: Cele 2 puncte pe care le selectezi reprezinta o diagonala si te folosesti de faptul ca punctele sunt sortate in ordine trigonometrica (uita'te cum "se misca" cealalta diagonala in functie de pozitia punctului 2 selectat fata de punctul 1).

[•Mishu91]

Din ce mi-am desenat eu, avand un punct fixat, pt celalalt punct, a2a diagonala poate ramane aceeasi ca la punctul anterior sau se poate muta in sens trigonometric in urmatorul punct. Dar nu stiu daca pentru toate cazurile se aplica regula asta 

[•CezarMocan]

Da, asta e.  (vezi ca se poate muta si mai mult de un punct)

[•Mishu91]

(vezi ca se poate muta si mai mult de un punct)

Atunci complexitatea nu poate sa sara de O(N^2)?

[•CezarMocan]

Pai nu, pentru ca tu in total pentru primul punct fixat faci N operatii ca sa il variezi pe al 2-lea, si ca sa se miste a 2-a diagonala sunt din nou maxim N (cred ca N, poate e mai mult dar e tot liniar) operatii, care se fac in timp ce misti al 2-lea punct. Ia-ti cateva exemple mai mari si o sa intelegi...

[•Mishu91]

Dap, mersi am inteles 

[L.E.] Care-i spirla la testu' 9 ca iau incorect in veselie

[L.E. 2] Fixed pentru cei care au probleme cu acest test aveti grija la cazul in care sunt mai multe puncte coliniare 

[•zloteanu.adrian]

Cod:

Urmatoarele N linii contin fiecare cate doua "numaere" intregi (Xi , Yi)

? ? ?