Re: Задача...

From

Илья Кантор (2:5020/175.2)

To

Viktor Karev

Date

2002-10-23T21:48:54Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

Wed Oct 23 2002 16:35, Viktor Karev wrote to Artem Rogetdinov:


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

 VK> Прямая, являющаяся продолжением одного из отрезков выпуклой
 VK> оболочки.
 VK> С одной стороны - пусто, с другой - все остальные точки.

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

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)