Спасибо большое! Только вот можете пояснить 3 пункт? Почему именно к половине имеющихся точек?

А чтобы выполнить:

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

Строго говоря, это неправильно.
Переделайте самостоятельно:
Нашли внутренние, их ci штук, внешних co=N-3-ci
И ищем минимум |co-ci|

Здравствуйте! Прошу прощения, что пишу по данному вопросу так поздно, но не могли бы вы все-таки откомментировать строки в вашей программе? Пытался самостоятельно разобраться, но пока получается неважно.

Немного подправил. Сделал, как говорил

Нашли внутренние, их ci штук, внешних co=N-3-ci
И ищем минимум |co-ci|

Вывожу минимальную разность
[code h=200]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>

#define N 100
typedef struct _point
{
double x;
double y;
}point;

// вычисляет положение точки D(x,y) относительно AB
// важен знак
double g(point a, point b, point d)
{
return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);
}

// лежат ли точки C и D с одной стороны прямой (AB)
// если результат g() одного знака, то с одной стороны!
bool f(point a, point b, point c, point d)
{
return g(a, b, c) * g(a, b, d) >= 0;
}

int main()
{
point* p = (point*)malloc(N*sizeof(point)); //выделим память в куче
int i,j,k,m; //переменные цикла
int ci, co; //количество внутри и снаружи
int cdelta; //их минимальная разность
point a,b,c; //для сохранения оптимальных точек
srand(time(NULL)); //инициализация генератора псевдослучайных чисел
for(i=0; i<N; i++) //заполним случайными числами [-100,99]
{
p[i].x = (rand()%200) - 100;
p[i].y = (rand()%200) - 100;
}
cdelta = N; //сначала считаем, что минимальная разность = N
for(i=0; i<N-2; i++) //перебираем все точки в трех циклах
{
for(j=i+1; j<N-1; j++)
{
for(k=j+1; k<N; k++)
{ //считаем точки, которые внутри
ci = 0; //обнуляем счетчик
for(m=0; m<N; m++) //по всем остальным точкам
{
if ((m != i) && (m != j) && (m != k))//обходим текущие
//проверяем, чтобы точка p[m] была по одну сторону
//со всеми вершинами относительно оставшейся стороны
//только тогда точка p[m] будет внутри
//если все три = true, только тогда инкрементируем счетчик внутренних
ci += f(p[i],p[j],p[k],p[m]) && f(p[j],p[k],p[i],p[m]) && f(p[k],p[i],p[j],p[m]);
}
co = N-3-ci; //количество внешних точек
if (abs(co-ci) < cdelta) //ищем минимальную разность
{
cdelta = abs(co-ci); //новая минимальная разность
a = p[i]; //сохраняем точки
b = p[j];
c = p[k];
}
}
}
}
printf("cdelta = %d\n", cdelta); //выведем минимальную разность

free(p); //освободим память
return 0;
}
[/code]
А вообще-то, математику надо знать, молодой человек

Теперь все понятно! Большое спасибо! Вы очень помогли!

Пожалуйста, объясните, каким образом эта строка
ci += f(p[i], p[j], p[k], p[m]) && f(p[j], p[k], p[i], p[m]) && f(p[k], p[i], p[j], p[m]);
И подпрограммы помогают понять местоположение точек относительно друг друга! Какие правила/теоремы используются? И еще
a = p[i]; //сохраняем точки
b = p[j];
c = p[k];
Как вывести abc на кран? cout не помогает

Вы думаете, я держу в голове программы двухлетней давности?
Сначала отвечу на последний вопрос: g вызывается из функции f
Далее, функции f возвращает true, если точка p[m] будет внутри треугольника, заданного точками p[i],p[j],p[k] в любой последовательности.
Если получим три true, то точка точно внутри, и добавляем единицу к количеству внутренних точек. Если будет false, то количество внутренних не изменится.
Теория - аналитическая геометрия. Смотрите самостоятельно.
Вывести на экран (у нас С, а не С++) можно при помощи printf, ну или (для С++) добавьте соответствующую h-ку. Тоже разберетесь самостоятельно

Что-то забыл подумать о дате)) Вроде понял. Но все же, если вдруг вспомните правила, по которым вы разобрались, лежит точка внутри или нет, то дайте знать) и еще: я учу с++, мне просто мало что показалось здесь отличным от с++ в вашем коде, как можно осознать что это си?
bool f(point a, point b, point c, point d)
{
return g(a, b, c) * g(a, b, d) >= 0;
}
В с++ разрешено так условия записать или нет?

Простое отличие Си от С++: используемые include-ы. Да и в тексте вопроса было сказано...

В с++ разрешено так условия записать или нет?

Конечно Никто не мешает считать код, как С++. Замените соответствующие include-ы, некоторые функции и вуаля...
Правила - векторная алгебра и аналитическая геометрия. Мне некогда Вам их рассказывать. Найдите самостоятельно.

Кстати, это не условие, а возврат true или false, в зависимости от того, одного ли знака результат указанных функций.