Помогите решить задачу про точки на плоскости.

[СергейКо]

Из заданного множества точек на плоскости выбрать три разные точки A, B, C, так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Помогите решить, пожалуйста.

[Romeo]

Самое просто решение, которое приходит - перебор всех троек точек, постройки трёх прямых на них по известной формуле "прямая, проходящая через две точки", и затем проверки всех остальных точек, что они лежат внутри треугольника. Последнее можно узнать, выполнив для каждой стороны треугольника проверку, что точка и свободная вершина треугольника находятся по одну сторону от прямой, проходящей через эту сторону.

Если это чем-то помогает, но не всё ясно, готов на дополнительные уточнения.

Но готовое решение вставить сюда не готов, хочу увидеть ответную работу

[СергейКо]

Мне бы,хотя б алгоритм нахождения,а треугольник я сам уже построю.

[Romeo]

Здесь нету алгоритма нахождения как такового. Ну по крайней мере в том решении, в котором я придумал. Просто перебор всех вариантов, подсчёт точек для каждого варианта и потом нахождения варианта с максимальным числом точек. Как перебрать все варианты выбора трёх точек из N? А вот так:

Код: Выделить всё

const int N = 10; // amount of points
int x[N], y[N]; // coordinates of points

EnterCoordinates(x, y, N);

for (int i = 0; i < N-2; ++i)
{
   for (int j = i+1; i < N-1; ++j)
   {
      for (int k = j+1; k < N; ++k)
      {
         // here we are analyzing one variant from a lot of possible ones
         // three selected points have indexies: i, j, k

         // this is "for" to check all not selected points
         for (int p = 0; p < N; ++p)
         {
            if (p != i && p != j && p != k)
            {
               // if we are here then point is not selected and should be checked whether it is in the triagle <i,j,k>
            }
         }
      }
   }
}

Это упрощённый набросок главного цикла. Теперь сюда нужно вставить формулы для расчёта расположения точек относительно построенных линий и иные необходимые вещи (подробнее в предыдущем посте).

[Albor]

Думаю, что не нужно рассматривать все точки множества, а только те, что находятся на внешней его границе. То есть, выбрать точки с с max/min координатами и рассчёты проводить для них.

[Romeo]

Думаю, не сложно подобрать примеры, когда выбор точек с min/max координатами не даст треугольника с максимальным количеством точек внутри. Но, в любом случае, я не спорю, что здесь можно придумать какие-то оптимизации. Я просто дал первое решение, пришедшее в голову. Пусть оно не оптимально, но гарантированно работает.

P.S. Кстати, рад тебя видеть, Albor. Что-то форум некоторое время вообще умершим был. Теперь снова ожил. Замечательно, что старые знакомые тоже о нём помнят

[Albor]

Я тоже рад. Форум хороший!

[Хыиуду]

Ностальгия прямо

[СергейКо]

Думаю, не сложно подобрать примеры, когда выбор точек с min/max координатами не даст треугольника с максимальным количеством точек внутри. Но, в любом случае, я не спорю, что здесь можно придумать какие-то оптимизации. Я просто дал первое решение, пришедшее в голову. Пусть оно не оптимально, но гарантированно работает.

P.S. Кстати, рад тебя видеть, Albor. Что-то форум некоторое время вообще умершим был. Теперь снова ожил. Замечательно, что старые знакомые тоже о нём помнят

А если ввел множество точек, построил треугольник, как мне определить какие точки входят в этот треугольник а какие нет?

[Albor]

Посмотрите здесь