Geometry

В тази секция ще разгледаме как можем да направим основни неща от геометрията ползвайки програмиране. Ще припомним как се намира разстояние между точки, лице на многоъгълник, как се прави ротация на точка около друга точка. Ще видим какво е насочено лице на триъгълник и как можем да го ползваме за проверка от коя страна на някаква права е дадена точка. Ще покрием и относително чести под-задачи, като например проверка за пресичане на права с права и права с окръжност, както и намиране на пресечната точка. Ще видим как да проверим дали точка е във вътрешността на многоъгълник и как ефективно да намерим изпъкналата обвивка на множество от точки.

Полезни теми, които можете да погледнете тук са Геометрия, а както и Двоично Търсене и Троично Търсене, които понякога можем да ползваме за да избегнем справянето с частни случаи, които възникват при някои геометрични задачи.

Задачите в секцията изискват само някои от изброените по-горе алгоритми, но по-нататък ще срещнем и други задачи, които включват останалите, като например Spectre, Towers, или Deathstars.