Количество треугольников с N точками внутри
Учитывая некоторые точки на плоскости (до 500 точек), нет 3 коллинеарных. Мы должны определить количество треугольников, вершины которых находятся в заданных точках и которые содержат ровно N точек внутри них. Как эффективно решить эту проблему? Наивный алгоритм O(n^4) слишком медленный. Есть ли лучший подход?
2 ответа
Вы можете попытаться представить треугольник как пересечение трех полупространств. Чтобы найти количество точек внутри треугольника A, B, C, сначала рассмотрим набор точек на одной стороне бесконечной линии в направлении AB. Пусть эти множества L (AB) и R(AB) для точек слева и справа. Точно так же вы делаете то же самое с другими двумя ребрами и строите наборы L(AC) и R (AC) и наборы L(BC) и R (BC).
Таким образом, количество точек в ABC будет количеством точек на пересечении L (AB), L(AC) и L(BC). (Возможно, вы захотите рассмотреть R(AB) вместо этого в зависимости от ориентации треугольника).
Теперь, если мы хотим рассмотреть полный набор из 500 баллов. Сначала возьмем все пары точек AB и построим множества L (AB) и R(AB). Это займет O(n^3) операций.
Затем мы проверяем все треугольники и находим пересечения трех наборов. Если мы используем некоторую структуру хеш-таблицы для наборов, то найти точки пересечения - это как поиск по хеш-таблице. Если L (AB) имеет l элементов, L(AC) имеет m элементов и L(BC) n элементов. Скажи l > m > n. Для каждой точки в L(BC) нам нужно выполнить поиск в L(AC) и L(BC), чтобы получить максимум 2n хеш-таблиц поиска.
Может быть быстрее рассмотреть геометрическую таблицу поиска. Разделите весь ваш домен на грубую сетку, скажем, 10 на 10. Затем мы можем поместить каждую точку в множество G(i,j). Затем мы можем разбить множества L (AB) на каждую ячейку сетки. Скажем, назовите эти множества L(AB,i,j) и R(AB,i,j). При тестировании на пересечениях сначала тренируются, чьи ячейки сетки лежат на пересечении. Это значительно уменьшает пространство поиска, и так как каждый набор L(AB,i,j) содержит меньше членов, будет меньше хеш-таблиц поиска.
На самом деле я недавно столкнулся с подобной проблемой, но единственное отличие заключалось в том, что было около 300 пунктов, и я решил ее с помощью набора битов (C++ STL). Для каждой пары точек, скажем (x[i],y[i]) и (x[j],y[j]), я сформировал набор битов<302>B[i][j] и B [i] [j] [k] хранит 1, если k-я точка находится над отрезком линии от точки i до точки j, иначе я бы сохранил 0.
Теперь методом грубой силы я получаю три точки, чтобы сформировать треугольник, скажем, (x[i],y[i]), (x[j],y[j]) и (x[k],y[k]), то точка, скажем z-я точка, будет внутри треугольника, если B[i][j][z]==B[i][j][k] && B[j][k][z]==B[j][k][i] && B[k][i][z]==B[k][i][j], потому что точка внутри треугольника будет показывать аналогичный знак со стороны треугольника как третьей точки треугольника (той, которая не на этой стороне). Таким образом, я получаю три битовые переменные P=B[i][j], Q=B[j][k] и R=B[k][i] и там бита там, и затем применяя функцию count(), чтобы дать мне активное число битов и, следовательно, количество точек в треугольнике. Но убедитесь, что вы изменили переменную P так, что она дает B[i][j][k]=1, если нет, тогда не принимайте поразрядно (~) этой переменной.
Хотя вышеупомянутое решение зависит от конкретной проблемы, я надеюсь, что это поможет. Это ссылка на проблему: http://usaco.org/current/index.php?page=viewproblem&cpid=660