546 Polig

[•astronomy]

Aici puteţi discuta despre problema Polig.

[•filipb]

Am citit articolul cu solutii si imi este ceva neclar la aceasta problema.
Daca retin ultimele 2 puncte pot intr-adevar sa verific ca niciodata sa nu ma intorc mai mult de 180 de grade ( oricare 3 puncte sa formeze un unghi < 180 ). Cu toate acestea, linia poligonala care se poate forma poate sa se intersecteze si nu se mai formeaza un poligon convex.

Iata o imagine elocventa:
http://infoarena.ro/problema/polig?action=download&file=desen.jpg

Se observa ca fiecare unghi dintre 3 puncte consecutive e < 180, si totusi ce se formeaza nu e poligon convex.
Imi scapa mie ceva? In conditiile astea, cum s-ar mai rezolva problema?

Cum pot sa pun o imagine direct pe forum ca sa fie mai usor de vazut? Am incercat sa atasez o imagine si dupa aia ce cale trebuie sa ii pun?

[•wefgef]

Ai dreptate Buru .

[•DITzoneC]

Am impresia ca daca parcurgi punctele sortate dupa x (sa zicem), nu poti sa ajungi la constructia aia.

[•astronomy]

Atentie, toate punctele au coordonata y > 0 si tu faci dinamica dupa ce sortezi punctele dupa unghiul cu axa Ox. Desenul tau nu respecta conditiile astea si cred ca solutia descrisa in articol este corecta.

[•filipb]

toate punctele au coordonata y > 0

 

Din moment ce au fost atatea punctaje maxime stiam ca solutia oficiala e corecta, insa nu stiam ce imi scapa mie.

[•ciprianf]

In articolul cu solutii se precizeaza si despre o solutie in N^2 log N, insa nu imi dau seama cam care ar fi aceasta. O stie cineva?

[•freak93]

Am sa-ti dau un hint pentru solutia N ^ 2 log N, ar fi cam aiurea sa postez rezolvarea. Se pastreaza dinamica initiala. Trebuie sa observi ca daca notezi cu A multimea k-urilor din care poate provine dinamica[ i ][ j ] si cu B multimea k-urilor din care poate provine dinamica[ i ][ j' ] atunci A este inclus in B sau invers.