Учитывая массив точек b [0..n-1], каждый из которых имеет координаты .x и .y. n может быть большим.Найти максимальное количество точек, содержащихся в прямоугольнике с заданной областью
Разработать эффективный алгоритм для проблемы: задайте область, найдите максимальное количество точек, содержащихся в прямоугольнике с данной областью.
Я хочу, чтобы это выполнялось по временной сложности O (n^2 * k), где k - максимальные точки в прямоугольнике или лучше.
Если у вас есть вершины треугольника, это очень просто. Вы можете решить кросс-продукт для каждой точки массива b.
Вы можете рассчитать Cross1 = [AO, AB], Cross2 = [BO, BC], Cross3 = [CO, CA].
Например, Cross1 = AO.x * AB.y - AO.y * AB.x.
Каждая переменная Cross1, Cross2, Cross3 должна быть одинаковой.
Вы проверяете это для каждой точки и подсчитываете точки на прямоугольник. Затем у вас есть kN = O(N).
Не думаю, что это отвечает на вопрос. Проблема заключается не в проверке того, какие точки находятся внутри данной формы, а в выборе и позиционировании фигуры для оптимизации количества точек в ней. (Если вопрос немного расплывчатый, лучше сначала попросить разъяснения, прежде чем вы начнете отвечать на него.) – m69
Приносим извинения, что прямоугольник должен быть выровнен по оси. – Algor7
Извините, вы не поняли постановку проблемы. Прямоугольник не указывается только для области, и мы должны найти все возможные прямоугольники той же области, а затем найти, какой прямоугольник имеет максимальные точки, содержащиеся в нем. Мы не заинтересованы в прямоугольнике, но интересуемся максимальным количеством точек. – Algor7
Домашнее задание, правильно? – m69
абсолютно нет ... это мое требование для проекта. – Algor7
@ Algor7 Вы должны дать некоторый контекст того, что представляет собой проект, он может многое рассказать об оптимизации (например, если набор точек может быть описан функцией). – ChatterOne