Diferente pentru preoni-2005/runda-3/solutii intre reviziile #17 si #20

Nu exista diferente intre titluri.

Diferente intre continut:

Articolul contine ideile de rezolvare ale problemelor propuse la ultima runda a concursului preONI ce s-a desfasurat pe data de 20 martie 2005, cat si comentarii legate de concurs. Si de aceasta data numarul de participanti a fost impresionat, cu siguranta datorita faptului ca in numai 5 zile incepe ONI!
Setul de probleme a fost mai greu de data aceasta, special pentru a testa concurentii cu probleme cat mai asemanatoare cu stilul ONI. Speram ca fiecare participant a invatat cate ceva in urma acestui concurs si asteptam pareri si sugestii pentru viitor pe "forum":http://http://forum.infoarena.ro/.
Setul de probleme a fost mai greu de data aceasta, special pentru a testa concurentii cu probleme cat mai asemanatoare cu stilul ONI. Speram ca fiecare participant a invatat cate ceva in urma acestui concurs si asteptam pareri si sugestii pentru viitor pe "forum":http://infoarena.ro/forum/.
h2. Clasele 9-10
Astfel, problema este rezolvabila in complexitate {$O(N*K)$}.
h3. Poligon
h3(#poligon). Poligon
Problema cere sa determinam cate puncte din cele $M$ sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in $O(N)$ daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostru (unghiurile sunt luate pozitive sau negative dupa cum cele $3$ puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e $0$ atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e $2*Pi$ atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti
sa va uitati pe urmatoarele pagini: "[1]":http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html "[2]":http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.