|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : €«мп Љ в®а 2:5020/175.2 23 Oct 2002 21:48:54
To : Viktor Karev
Subject : Re: Задача...
--------------------------------------------------------------------------------
Wed Oct 23 2002 16:35, Viktor Karev wrote to Artem Rogetdinov:
>> Имеется плоскость с заданными на ней точками (координатами). Hужно
>> провести прямую через две точки этой плоскости (выбираются из заданных),
>> чтобы количество точек с одной стороны минимально отличалось от
>> количества точек с другой стороны. Мне кажется или эта задача решается
>> только полным перебором?
VK> Прямая, являющаяся продолжением одного из отрезков выпуклой
VK> оболочки.
VK> С одной стороны - пусто, с другой - все остальные точки.
Это - классическая задача NP. Разделить сумму на 2 возможно равные части..
Решается перебором, можно при участии дин. программирования.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Задача... |
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 |
|
|
