Страница 1 из 1

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

Добавлено: 25 фев 2013, 08:48
СергейКо
Из заданного множества точек на плоскости выбрать три разные точки A, B, C, так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Помогите решить, пожалуйста.

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

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

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

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

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

Добавлено: 25 фев 2013, 20:18
СергейКо
Мне бы,хотя б алгоритм нахождения,а треугольник я сам уже построю.

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

Добавлено: 25 фев 2013, 21:11
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>
            }
         }
      }
   }
}
Это упрощённый набросок главного цикла. Теперь сюда нужно вставить формулы для расчёта расположения точек относительно построенных линий и иные необходимые вещи (подробнее в предыдущем посте).

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

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

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

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

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

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

Добавлено: 26 фев 2013, 17:43
Albor
Я тоже рад. Форум хороший!

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

Добавлено: 28 фев 2013, 11:44
Хыиуду
Ностальгия прямо :)

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

Добавлено: 24 мар 2013, 22:05
СергейКо
Romeo писал(а):Думаю, не сложно подобрать примеры, когда выбор точек с min/max координатами не даст треугольника с максимальным количеством точек внутри. Но, в любом случае, я не спорю, что здесь можно придумать какие-то оптимизации. Я просто дал первое решение, пришедшее в голову. Пусть оно не оптимально, но гарантированно работает.

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

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

Добавлено: 25 мар 2013, 08:25
Albor
Посмотрите здесь