h2(#aplicatia-17). Aplicaţia 17: Texan (Baraj ONI, 2005)

!> transformari-geometrice?aplicatie-17.1.png 75%!
 

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).

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)$.