Помогите алгоритм составить [Версия для КПК]

MaZaFaKa46

23-12-2008, 21:48

Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разность между
колличествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках

помогите выложите алгоритм а то яне шарю в этом

pva

24-12-2008, 10:05

Полным перебором очень долго будет. Предлагаю так: Пусть есть N точек, тогда найти такие треугольники, внутри которых abs(количество_точек - (N-3)/2) -> min. Дальше можно уменьшить количество переборов следующим образом:
1. Есть множество точек point[i]. Перебираем точки №1 и №2 чтоб были неодинаковые point[i]!=point[j], а вот точку №3 - чтобы съэкономить время выбираем хитрым образом.
2. Держим 2 сортированных списка - по тангенсу угла A при точке №1 и тангенсу угла B при точке №2.
2.1. Берём минимальный тангенс A, делаем во втором списке (N-3)/2 шагов (если столько возможно), так чтобы угол A был не меньше начального. Запомнили точку, посчитали сколько осталось шагов (K1 = количество_точек - (N-3)/2).
2.2. Двигаемся по первому списку, если K1>0, тогда уменьшаем A при не меньшем B, иначе увеличиваем. Потом по списку B так же, и так далее, пока не проползём все списки.
2.3. По пути запоминаем наилучшый достигнутый результат. Таким образом, мы пройдём все "лучшие" варианты с точкой №3. Причём путь будет всегда близко к дуге, на которой количество точек внутри примерно (на сколько это возможно) равно (N -3)/2