ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      23 Oct 2002  14:03:02
 To : €«мп Љ ­в®а
 Subject : Задача...
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Илья Кантор to Viktor Karev:
 
  >>> Имеется плоскость с заданными на ней точками (координатами). Hужно
  >>> провести  прямую через две точки этой плоскости (выбираются из
  >>> заданных), чтобы  количество точек с одной стороны минимально
  >>> отличалось от количества точек с  другой стороны. Мне кажется или эта
  >>> задача решается только полным перебором?
 
 Для простоты рассмотрим случай общего положения точек (никакие три не лежат на
 одной прямой). Тогда берешь любую точку и прямую через нее проходящую, и
 начинаешь эту прямую вращать (проводить через все другие точки), пока не
 добьешься требуемого условия. Сложность порядка O(n), где n - число точек.
 
  ИК>  Это - классическая задача NP. Разделить сумму на 2 возможно равные
  ИК> части.. Решается перебором, можно при участии дин. программирования.
 
 Причем тут сумма? Указаная тобой задача к оригинальной никакого отношения не
 имеет.
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.8
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    Задача...   Artem Rogetdinov   22 Oct 2002 10:19:00   Re: Задача...   Viktor Karev   23 Oct 2002 16:35:06   Re: Задача...   €«мп Љ ­в®а   23 Oct 2002 21:48:54   Задача...   Max Alekseyev   23 Oct 2002 14:03:02   Задача...   Andrew Plyako   24 Oct 2002 02:42:14   Задача...   Max Alekseyev   23 Oct 2002 18:54:12   Задача...   Andrew Plyako   24 Oct 2002 08:51:46   Задача...   Max Alekseyev   24 Oct 2002 12:19:20   Задача...   Andrew Plyako   25 Oct 2002 05:39:32