Dados N polígonos anidados que no se intersecan y una array 2D arr[][] de pares , donde cada celda de la array representa las coordenadas de los vértices de un polígono. La tarea es encontrar la cantidad de polígonos que se encuentran dentro de cada polígono.
Ejemplos:
Entrada: N = 3, array[][][] = {{{-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}}}
Salida: 1 0 2
Explicación:
- El polígono representado en el índice 0 es el polígono de color verde que se muestra en la imagen de arriba.
- El polígono representado en el índice 1 es el polígono de color azul que se muestra en la imagen de arriba.
- El polígono representado en el índice 2 es el polígono de color amarillo que se muestra en la imagen de arriba.
Por lo tanto, hay 1 polígono dentro del polígono de índice 0, 0 polígonos dentro del polígono de índice 1 y 2 polígonos dentro del polígono de índice 2.
Enfoque: El problema anterior se puede resolver con base en las siguientes observaciones:
- Se puede observar que el polígono que se encuentra afuera tendrá las coordenadas X más grandes . Las coordenadas X máximas del polígono disminuirán, ya que uno irá hacia el interior, dado que los polígonos están anidados y no se intersecan.
- Por lo tanto, ordenar los polígonos por la coordenada X máxima dará el orden correcto de los polígonos que se encuentran.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D, por ejemplo , maximumX[][] de tamaño N*2 para almacenar el par de coordenadas X máximas de un polígono y el valor de índice del polígono.
- Itere sobre la array arr[][] usando la variable, realizo los siguientes pasos:
- Inicialice una variable, digamos maxX, para almacenar la coordenada X máxima del polígono actual .
- Itere sobre la array arr[i] usando la variable j y en cada iteración actualice maxX como maxX = max(maxX, arr[i][j][0]).
- Asigne el par {maxX, i} a maximumX[i].
- Ordene la array de pares en orden descendente por el primer elemento utilizando un comparador personalizado.
- Inicialice una array, digamos res[], para almacenar el recuento de polígonos que se encuentran dentro del polígono actual.
- Itere sobre el rango [0, N-1] usando la variable i y en cada iteración asigne Ni-1 a res[maximumX[i][1]], ya que hay polígonos de Ni-1 dentro del máximoX[i][ 1] polígono .
- Finalmente, después de completar los pasos anteriores, imprima la array res[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
// Function to calculate maximum sum
void findAllPolygons(int N,
vector<vector<vector<int> > > arr)
{
// Stores the maximum X co-
// ordinate of every polygon
vector<pair<int, int> > maximumX(N);
// Traverse the array arr[][]
for (int i = 0; i < N; i++) {
// Stores the max X co-
// ordinate of current
// polygon
int maxX = INT_MIN;
// Traverse over the vertices
// of the current polygon
for (int j = 0; j < arr[i].size(); j++) {
// Update maxX
maxX = max(maxX, arr[i][j][0]);
}
// Assign maxX to maximumX[i][0]
maximumX[i].first = maxX;
// Assign i to maximumX[i][1]
maximumX[i].second = i;
}
// Sort the array of pairs
// maximumX in descending
// order by first element
sort(maximumX.rbegin(), maximumX.rend());
// Stores the count of
// polygons lying inside
// a polygon
vector<int> res(N, 0);
// Traverse the maximumX array
for (int i = 0; i < N; i++) {
// Update value at
// maximumX[i][1] in
// res
res[maximumX[i].second] = N - 1 - i;
}
// Print the array array res
for (int i = 0; i < N; i++) {
cout << res[i] << " ";
// System.out.print(res[i] + " ");
}
}
// Driver Code
int main()
{
int N = 3;
vector<vector<vector<int> > > 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 } }
};
findAllPolygons(N, arr);
return 0;
}
// The code is contributed by Gautam goel (gautamgoel962)
Java
// Java program for above approach
import java.util.*;
class GFG {
// Function to sort a 2D
// array using custom a comparator
public static void sort2d(int[][] arr)
{
Arrays.sort(arr, new Comparator<int[]>() {
public int compare(final int[] a,
final int[] b)
{
if (a[0] < b[0])
return 1;
else
return -1;
}
});
}
// Function to calculate maximum sum
static void findAllPolygons(int N,
int[][][] arr)
{
// Stores the maximum X co-
// ordinate of every polygon
int[][] maximumX = new int[N][2];
// Traverse the array arr[][]
for (int i = 0; i < N; i++) {
// Stores the max X co-
// ordinate of current
// polygon
int maxX = Integer.MIN_VALUE;
// Traverse over the vertices
// of the current polygon
for (int j = 0; j < arr[i].length; j++) {
// Update maxX
maxX = Math.max(maxX, arr[i][j][0]);
}
// Assign maxX to maximumX[i][0]
maximumX[i][0] = maxX;
// Assign i to maximumX[i][1]
maximumX[i][1] = i;
}
// Sort the array of pairs
// maximumX in descending
// order by first element
sort2d(maximumX);
// Stores the count of
// polygons lying inside
// a polygon
int[] res = new int[N];
// Traverse the maximumX array
for (int i = 0; i < N; i++) {
// Update value at
// maximumX[i][1] in
// res
res[maximumX[i][1]] = N - 1 - i;
}
// Print the array array res
for (int i = 0; i < N; i++) {
System.out.print(res[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int[][][] 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 } }
};
findAllPolygons(N, arr);
}
}
Producción
1 0 2
Complejidad de Tiempo: O(M + N log N), Donde M tamaño máximo de un polígono
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hritikrommie y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA