|
Titlul: 546 Polig Scris de: Airinei Adrian din Octombrie 07, 2007, 16:03:04 Aici puteţi discuta despre problema Polig (http://infoarena.ro/problema/polig).
Titlul: Răspuns: 546 Polig Scris de: Filip Cristian Buruiana din Decembrie 15, 2007, 14:50:02 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? Titlul: Răspuns: 546 Polig Scris de: Andrei Grigorean din Decembrie 15, 2007, 14:56:09 Ai dreptate Buru :P.
Titlul: Răspuns: 546 Polig Scris de: Adrian Diaconu din Decembrie 15, 2007, 15:11:19 Am impresia ca daca parcurgi punctele sortate dupa x (sa zicem), nu poti sa ajungi la constructia aia.
Titlul: Răspuns: 546 Polig Scris de: Airinei Adrian din Decembrie 15, 2007, 15:29:31 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.
Titlul: Răspuns: 546 Polig Scris de: Filip Cristian Buruiana din Decembrie 15, 2007, 15:52:26 Citat toate punctele au coordonata y > 0 :shock: Din moment ce au fost atatea punctaje maxime stiam ca solutia oficiala e corecta, insa nu stiam ce imi scapa mie. Titlul: Răspuns: 546 Polig Scris de: Farcasanu Alexandru Ciprian din Decembrie 16, 2010, 18:40:09 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?
Titlul: Răspuns: 546 Polig Scris de: Adrian Budau din Decembrie 17, 2010, 08:26:35 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.
|