Ни как не могу придумать толковый алгоритм к этой задаче
: Из заданного множества точек на плоскости выбрать такие три точки А, В, С, чтобы внутри треугольника АВС содержалось максимальное количество точек этого множества

поподробнее про выпуклую оболочку - обоснование, что так сокращается перебор?

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

в принципе я знаю метод сужения полного перебора, но он подходит только для общего случая, т.е. есть случаи, где этот метод не будет работать, и даст только лишние вычисления. Но мне кажется, что это тоже по большому счету обычный перебор, Хочется что-нить красивое.

Спасибо за пример mikhail_n, а то я ужо картинку накидал :))

для miksoft
>кстати, а о каком количестве точек идет речь? - дофига в разумных пределах, ну пусть хоть 1000
>известно ли что-нибудь про их распределение на плоскости? - абсолютно произвольное (ну ес-но бесконечные координаты - это не разумно и только для математиков - теоретиков)

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

разумно, но так исключается достаточно малое количество точек, если я все правильно понял...

Мой вариант сокращения перебора таков:
допустим на некотором этапе перебора получен треугольник содержащий в себе MAX точек тогда:
на очередном этапе перебора выбрана пара точек D и E. Прямая проходящая через эти точки делит плоскость на две полуплоскоси. В общем случае оказываются точки "слева" и "справа" от это прямой. Дык Вод. если с одной стороны (или что еще лучше с обоих) количество точке меньше, чем MAX, то они (эти точки) исключаются из рассмотрения, на кондидатуру третьей точки.

забыл пояснить.

так как если выбирать трутью точку в этой (отсекаемой) полуплоскости - треугольник полностью находится в этой полуплоскости - а там и так точек меньше.
ЗЫ на рисунке отсекаемая полуплоскость помечена красным квадратом

Но все равно хотелось бы чего-нить покрасивше.

Lepsikнарод - есть же топик программирование вы бы еще в фокспро запостили

я на C програмлю - мне сюда роднее