ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Kuznetsov                      2:5030/566.13  25 Feb 2002  22:20:00
 To : All
 Subject : Проблема
 -------------------------------------------------------------------------------- 
 

 
 Тут возникла такая проблема: найти пересечение\объединение 2-х
 выпуклых многоугольников (у одного M вершин у другого N) за время О(M+N).
 Единственное, что я смог придумать - это найти пересечение всех сторон
 многоугольников. Hайденные точки образуют выпуклый многоугольник, поэтому
 просто ищем его площадь - она и будет ответом. Т.к пересечение сторон я умею
 искать за О(M+N) то условие на время выполныется. Тут есть всего одна проблема
 - пересечение отрезков ищется сильно неточно следовательно и площадь находится
 с большой погрешностью!
 Так вот хочется либо улучшения "моего" алгоритма либо чего-нибудь другого.
 Подкинте решение пожалуйста!
 --- GoldED+/W32
 
 ---
  * Origin: Ya! (2:5030/566.13)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор