Найдите количество многоугольников, лежащих внутри каждого заданного многоугольника на декартовой плоскости.

Даны N непересекающихся вложенных многоугольников и двумерный массив arr[][] пар, где каждая ячейка массива представляет координаты вершин многоугольника. Задача состоит в том, чтобы найти количество полигонов, лежащих внутри каждого полигона.

Примеры:

Input: N = 3, arr[][][] = {{{-2, 2}, {-1, 1}, {2, 2}, {2, -1}, {1, -2}, {-2, -2}}, {{-1, -1}, {1, -1}, {1, 1}}, {{3, 3}, {-3, 3}, {-3, -3}, {3, -3}}}
Output: 1 0 2
Explanation:

1. The polygon represented at index 0, is the green-colored polygon shown in the picture above.
2. The polygon represented at index 1, is the blue-colored polygon shown in the picture above.
3. The polygon represented at index 2, is the yellow-colored polygon shown in the picture above.

Therefore, there is 1 polygon inside the polygon at index 0, and 0 polygons inside the polygon at index 1, and 2 polygons inside the polygon at index 2.
 

Подход: Вышеупомянутая проблема может быть решена на основе следующих наблюдений:

1. Можно заметить, что многоугольник, лежащий снаружи, будет иметь наибольшие координаты X. Максимальные X-координаты полигона будут уменьшаться по мере продвижения внутрь, так как дано, что полигоны вложены друг в друга и не пересекаются.
2. Следовательно, сортировка полигонов по максимальной координате X даст правильный порядок лежащих полигонов.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте 2D-массив, скажем, maxX[][] размера N*2 , чтобы хранить пару максимальных X-координат многоугольника и значение индекса многоугольника.
• Перебирая массив arr[][] с помощью переменной, я выполняю следующие шаги:
  • Инициализируйте переменную, скажем , maxX, для хранения максимальной координаты X текущего многоугольника .
  • Перебрать массив arr[i] с помощью переменной j и на каждой итерации обновить maxX как maxX = max(maxX, arr[i][j][0]).
  • Присвойте паре {maxX, i} значение maxX[i].
• Отсортируйте массив пар в порядке убывания по первому элементу с помощью пользовательского компаратора.
• Инициализируйте массив, скажем, res[], для хранения количества полигонов, лежащих внутри текущего полигона.
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и на каждой итерации присваивайте Ni-1 значение res[maximumX[i][1]], так как внутри maxX[i][N] находятся полигоны Ni-1 . 1] ^-й полигон.
• Наконец, после выполнения вышеуказанных шагов выведите массив res[] в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M + N log N), где M максимальный размер многоугольника
Вспомогательное пространство: O(N)