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 iniţ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 măsura unghiului $BOB’$ este de $60$ de grade. Menţionăm că aceasta a fost una dintre cele mai dure probleme de la selecţia lotului de anul acesta. O rezolvare de complexitate $O(N^2^)$ a fost de ajuns pentru punctajul maxim, dar facem observaţia că intersecţia a două poligoane convexe se poate face în complexitate $O(N)$.

 
h2(#aplicatia-18). Aplicaţia 18: dotNet (.campion, 2004)
 
bq. Se dau $N$ puncte în planul euclidian prin coordonatele lor, numere întregi. Apoi se efectuează $M$ operaţii asupra tuturor punctelor, într-o ordine dată $(1 ≤ N ≤ 100 000, 0 ≤ M ≤ 10 000)$. O operaţie poate fi de două tipuri: de translaţie sau de rotaţie. Într-o operaţie de rotaţie, punctele sunt rotite în jurul originii cu un anumit număr de grade în sens trigonometric. Într-o operaţie de translaţie, originea este mutată în alt punct relativ la originea curentă şi coordonatele celorlalte puncte sunt modificate astfel încât să reprezinte aceleaşi puncte relativ la noua origine. Scrieţi un program care calculează coordonatele tuturor punctelor după cele $M$ operaţii.
 
h3. Rezolvare:
 
Folosim scrierea operaţiilor de translaţie si rotaţie ca produs de  matrici. Dacă vrem să rotim punctul $(x, y)$ în jurul punctului de coordonate $(0, 0)$ după un unghi <tex> \alpha </tex> atunci putem scrie:
 
<tex> \left[ \begin{array}{c} x_1 \\ y_1 \\ 1 \end{array} \right] = \begin{bmatrix} cos \alpha & -sin \alpha & 0 \\ sin \alpha & cos \alpha & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \left[ \begin{array}{c} x \\ y \\ 1 \end{array} \right] </tex>
 
Iar translaţia o putem scrie ca:
 
<tex> \left[ \begin{array}{c} x_2 \\ y_2 \\ 1 \end{array} \right] = \begin{bmatrix} 1 & 0 & dx \\ 0 & 1 & dy \\ 0 & 0 & 1 \end{bmatrix} \times \left[ \begin{array}{c} x \\ y \\ 1 \end{array} \right] </tex>
 
Astfel transformarea pentru un punct devine un produs de matrici care la sfârşit se înmulţeşte cu un vector ce reprezintă coordonatele punctului pe care vrem să îl transformăm. Pentru că transformarea compusă este aceeaşi pentru fiecare dintre cele $N$ puncte, determinăm matricea care o reprezintă o singură dată şi apoi o putem aplica pe rând fiecărui punct. Algoritmul are complexitatea $O(N + M)$.
Menţionăm că o problemă similară apare pe SGU sub numele de wizards, diferenţa fiind că acolo operaţiile sunt în spaţiul tridimensional, dar rezolvarea este aproape identică.
 
 
h2(#bibliografie). Bibliografie
 
# Nicolescu, Boskoff, _Probleme practice de geometrie_, Ed. Tehnică, Bucureşti, 1990
# 'Cut the Knot':http://www.cut-the-knot.org
# 'Timus':http://acm.timus.ru/
# 'UVa':http://uva.onlinejudge.org/
# 'TopCoder':http://www.topcoder.com/tc
# 'SGU':http://acm.sgu.ru
# Dijkstra’s EWDs