Страница 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