Задача...

From

Max Alekseyev (2:5015/60)

To

Илья Кантор

Date

2002-10-23T14:03:02Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Илья !

Replying to a message of Илья Кантор to Viktor Karev:

 >>> Имеется плоскость с заданными на ней точками (координатами). Нужно
 >>> провести  прямую через две точки этой плоскости (выбираются из
 >>> заданных), чтобы  количество точек с одной стороны минимально
 >>> отличалось от количества точек с  другой стороны. Мне кажется или эта
 >>> задача решается только полным перебором?

Для простоты рассмотрим случай общего положения точек (никакие три не лежат на одной прямой). Тогда берешь любую точку и прямую через нее проходящую, и начинаешь эту прямую вращать (проводить через все другие точки), пока не добьешься требуемого условия. Сложность порядка O(n), где n - число точек.

 ИК>  Это - классическая задача NP. Разделить сумму на 2 возможно равные
 ИК> части.. Решается перебором, можно при участии дин. программирования.

Причем тут сумма? Указаная тобой задача к оригинальной никакого отношения не имеет.

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)