ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anthone Tikhonov                     2:5020/400     21 Mar 2003  15:01:36
 To : Eldar Ulukhanov
 Subject : Пересение прямоугольников
 -------------------------------------------------------------------------------- 
 

  EU> Есть множество прямоугольков на плоскости и надо найти всевозможные
  EU> попарные пересечения этих прямоугольников.
  EU> Эту задачу можно решить перебрав двойным циклом все возможные пары
  EU> прямоугольников. Однако при большом количестве прямогульников на это
  EU> тратиться много времени.
 
 Я надеюсь, стороны всех прямоугольников параллельны друг другу?
 Тогда сразу приходит мысль ввести прямоугольную сетку, проведя через каждую
 сторону прямую линию. Потом это все записать в массив NxN, в каждой ячейке
 которого фиксировать цифру - сколько прямоуг. в ней пересекаются
 А, все равно N^2 получается...
 Hе знаю как решать. Просто пообщаться хотелось...
 И вообще, всевозможных пересечений может быть N^2 - т.е. ответ задачи имеет
 такую длину. Т.е. быстрее не решить. Хорошо, не e^N
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Пересение прямоугольников   Eldar Ulukhanov   20 Mar 2003 20:54:00   Пересение прямоугольников   Anthone Tikhonov   21 Mar 2003 15:01:36   Re: Пересение прямоугольников   Anatoly Saveliev   21 Mar 2003 15:19:38   Re: Пересение прямоугольников   Sergey Andrianov   27 Mar 2003 10:15:34