h3. Rezolvare:
Pornim de la presupunerea intuitivă că cel mai mare pătrat ce se poate plasa în interiorul unui triunghi trebuie să aibă una din laturi pe o latură a triunghiului. Astfel, pentru a determina pătratul de arie maximă avem trei posibilităţi de aşezare pe laturile triunghiului. Pentru o aşezare fixată putem afla uşor pătratul maxim din interiorul triunghiului ce are două varfuri pe latura $BC$. O modalitate ar fi să desenăm un pătrat $M’N’P’Q’$ ce are punctele $Q’$ şi $P’$ pe semidreapta $[BC$ şi punctul $M’$ pe semidreapta $[BA$. După care, luăm punctul $N$ ca intersecţie a dreptei $BN’$ cu $AC$. Găsim pătratul $MNPQ$ ca fiind omoteticul pătratului $M’N’P’Q’$ după omotetia de centru $B$ şi raport $BN / BN’$. Altă modalitate de construcţie a pătratului ar fi cea prezentată în a doua figură, adică: se construieşte în exterior, pe latura $BC$ a triunghiului, un pătrat $BCQ’P’$, se determineă punctele $P$ şi $Q$ ca şi intersecţii al segmentului $AQ’$ cu $BC$ şi al segmentului $AP’$ cu $BC$. Pătratul $MNPQ$ va fi omoteticul pătratului $BCP’Q’$, după omotetia de centru $A$ şi raport $QP / BC$.
Pornim de la presupunerea intuitivă că cel mai mare pătrat ce se poate plasa în interiorul unui triunghi trebuie să aibă una din laturi pe o latură a triunghiului. Astfel, pentru a determina pătratul de arie maximă avem trei posibilităţi de aşezare pe laturile triunghiului. Pentru o aşezare fixată putem afla uşor pătratul maxim din interiorul triunghiului ce are două varfuri pe latura $BC$. O modalitate ar fi să desenăm un pătrat $M’N’P’Q’$ ce are punctele $Q’$ şi $P’$ pe semidreapta $[BC$ şi punctul $M’$ pe semidreapta $[BA$. După care, luăm punctul $N$ ca intersecţie a dreptei $BN’$ cu $AC$. Găsim pătratul $MNPQ$ ca fiind omoteticul pătratului $M’N’P’Q’$ după omotetia de centru $B$ şi raport $BN / BN’$. Altă modalitate de construcţie a pătratului ar fi cea prezentată în a doua figură, adică: se construieşte în exterior, pe latura $BC$ a triunghiului, un pătrat $BCQ’P’$, se determină punctele $P$ şi $Q$ ca şi intersecţii al segmentului $AQ’$ cu $BC$ şi al segmentului $AP’$ cu $BC$. Pătratul $MNPQ$ va fi omoteticul pătratului $BCP’Q’$, după omotetia de centru $A$ şi raport $QP / BC$.
h2(#aplicatia-15). Aplicaţia 15: 'Arhipelago':http://acm.sgu.ru/problem.php?contest=0&problem=120 (SGU)
bq. Se dau coordonatele a două vârfuri ale unui poligon regulat de $N$ laturi. Se cere, dacă ştiţi pe $N$, cele două perechi de coordonate şi $N{~1~}$, $N{~2~}$ indicii celor două puncte pe poligon, să determinaţi coordonatele tuturor celor $N$ vârfuri.
h3. Rezolvare:
Fie $O$ centrul cercului circumscris poligonului regulat. Dacă notăm $A$ şi $B$ cele două puncte, atunci putem uşor să determinăm măsura unghiului $AOB$ pe care o notăm cu $alfa$. Triunghiul $AOB$ este isoscel şi ştim că are la bază unghiuri de măsură $beta = (180 – alfa) / 2$. Pentru a determina punctul $O$ vom roti dreapta $AB$ în jurul lui $A$ după un unghi $beta$, şi vom roti dreapta $AB$ în jurul lui $B$ după un unghi $beta$. Cele două drepte ce rezultă din cele două rotaţii se vor intersecta în punctul $O$. Astfel, am găsit centrul cercului circumscris poligonului, pentru a găsi punctele lui îi aplicăm vârfului $A$ rotaţiile de centru $O$ şi unghiuri $360K/N$ unde $K$ ia toate valorile naturale de la $1$ la $N$.
h2(#aplicatia-16). Aplicaţia 16: 'Geometrical dreams':http://acm.timus.ru/problem.aspx?space=1&num=1046 (Timus)
bq. Pe laturile unui poligon $A{~1~}A{~2~}...A{~N~}$ (vârfurile $A{~i~}$ sunt numerotate în ordine trigonometrică), se construiesc în exterior triunghiurile isoscele $A{~i~}M{~i~}A{~i+1~}$, iar unghiul $A{~i~}M{~i~}A{~i+1~} = alfa{~i~}$ (aici $A{~N+1~} = A{~1~}$). Suma măsurilor unghiurilor $alfa{~i~}$ nu este multiplu de $360$ de grade. Dacă ni se dau $N ≤ 50$, coordonatele punctelor $M{~i~}$ şi unghiurile $alfa{~i~}$, scrieţi un program care ne dă coordonatele vârfurilor poligonului.
h3. Rezolvare:
Aşa cum am văzut în partea teoretică, o compunere de mai multe rotaţii are ca rezultat o rotaţie al cărei unghi este suma unghiurilor rotaţiilor parţiale. Dacă pornim cu punctul $A{~1~}$ şi îl rotim în jurul lui $M{~1~}$ cu un unghi $alfa{~1~}$, după care luăm punctul rezultat şi îl rotim în jurul lui $M{~2~}$ cu unghiul $alfa{~2~}$ şi aşa mai departe până când am rotit pe $A{~1~}$ în punctelor $M{~1~}$, $M{~2~}$, ... $M{~n~}$. Efectuând aceşti paşi vom obţine pe rând vârfurile poligonului, iar la sfârşit $A{~1~}$ va ajunge din nou în poziţia iniţială. Acest procedeu este de fapt o serie de rotaţii, şi vedem că aplicarea lui asupra lui $A{~1~}$ îl lasă neschimbat. Cum suma măsurilor unghiurilor de rotaţie nu este multiplu de $360$ de grade, înseamnă că rotaţia nu este trivială, iar o rotaţie netrivială are ca punct fix doar centrul ei. Aşadar putem lua un punct oarecare în plan asupra căruia aplicăm procedeul şi vom obţine imaginea lui. Folosind aceste două puncte şi $alfa = suma de alfa{~i~}$ ca unghi de rotaţie, putem determina centrul $A{~1~}$ de rotaţie. După care efectuând transformările asupra lui $A{~1~}$ obţinem celelalte puncte ale poligonului.
h2(#aplicatia-17). Aplicaţia 17: Texan (Baraj ONI, 2005)
bq. Se dă un poligon convex de $N$ vârfuri $(3 ≤ N ≤ 700)$. Se cere să se determine un triunghi echilateral cu vârfurile aparţinând laturilor poligonului convex.
h3. Rezolvare:
Luăm un punct $O$ pe o latură a poligonului, rotim întreg poligonul în jurul acestui punct 60 de grade în sens trigonometric. Poligonul rotit va intersecta poligonul îniţial într-un nou punct B. Acest punct B îl rotim în jurul lui O cu 60 de grade în sens orar, rezultatul este un punct B’ care evident aparţine poligonului iniţial. Acum triunghiul OBB’ este echilateral pentru că OB = OB’ şi masura unghiului BOB’ este de 60 de grade. Menţionăm că aceasta a fost una dintre cele mai dure probleme de la selectia lotului de anul acesta.O rezolvare de complexitate O(N^2) a fost de ajuns pentru ca autorul să obţină punctajul maxim la ONIbyNet, dar facem observaţia că intersecţia a două poligoane convexe se poate face în complexitate O(N).
