Dada una array 2D rectángulo[][] que representa los vértices de un rectángulo {(0, 0), (L, 0), (0, B), (L, B)} de dimensiones L * B , y otra array 2D , puntos[][] de tamaño N en un sistema de coordenadas cartesianas. Dibuja una línea horizontal paralela al eje X y una línea vertical paralela al eje Y desde cada punto de la array dada. La tarea es contar todos los rectángulos posibles presentes dentro del rectángulo dado.
Ejemplos :
Entrada: Rectángulo[][] = {{0, 0}, {5, 0}, {0, 5}, {5, 5}}, puntos[][] ={{1, 2}, {3, 4}}
Salida: 9
Explicación:
Dibuje una línea horizontal y una línea vertical en los puntos {1, 2} y los puntos {3,4}._ _ _ _ _ 5|_|_ _|_ _| 4| | |3,4| 3|_|_ _|_ _| 2| |1,2| | 1|_|_ _|_ _| 0 1 2 3 4 5Por lo tanto, la salida requerida es 9.
Entrada: Rectángulo[][] = {{0, 0}, {4, 0}, {0, 5}, {4, 5}}, puntos[][] = {{1, 3}, {2, 3}, {3, 3}}
Salida: 12
Enfoque : la idea es atravesar la array y contar todas las líneas horizontales y verticales distintas que pasan por la array de puntos[][]. Finalmente, devuelva el valor de la multiplicación de (recuento de la línea horizontal distinta – 1) * (recuento de líneas verticales – 1) . Siga los pasos a continuación para resolver el problema:
- Cree dos conjuntos , digamos cntHor , cntVer para almacenar todas las líneas horizontales y verticales distintas que pasan por la array de puntos[][] .
- Atraviesa la array de puntos[][].
- Cuente todas las líneas horizontales distintas usando el conteo de elementos en cntHor .
- Cuente todas las líneas verticales distintas usando el conteo de elementos en cntVer .
- Finalmente, imprima el valor de (recuento de elementos en cntHor – 1) * (recuento de elementos en cntVer – 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the count
// of rectangles
int cntRect(int points[][2], int N,
int rectangle[][2])
{
// Store distinct
// horizontal lines
unordered_set<int> cntHor;
// Store distinct
// Vertical lines
unordered_set<int> cntVer;
// Insert horizontal line
// passing through 0
cntHor.insert(0);
// Insert vertical line
// passing through 0.
cntVer.insert(0);
// Insert horizontal line
// passing through rectangle[3][0]
cntHor.insert(rectangle[3][0]);
// Insert vertical line
// passing through rectangle[3][1]
cntVer.insert(rectangle[3][1]);
// Insert all horizontal and
// vertical lines passing through
// the given array
for (int i = 0; i < N; i++) {
// Insert all horizontal lines
cntHor.insert(points[i][0]);
// Insert all vertical lines
cntVer.insert(points[i][1]);
}
return (cntHor.size() - 1) *
(cntVer.size() - 1);
}
// Driver Code
int main()
{
int rectangle[][2] = {{0, 0}, {0, 5},
{5, 0}, {5, 5}};
int points[][2] = {{1, 2}, {3, 4}};
int N = sizeof(points) / sizeof(points[0]);
cout<<cntRect(points, N, rectangle);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to get the count
// of rectangles
public static int cntRect(int points[][], int N,
int rectangle[][])
{
// Store distinct
// horizontal lines
HashSet<Integer> cntHor = new HashSet<>();
// Store distinct
// Vertical lines
HashSet<Integer> cntVer = new HashSet<>();
// Insert horizontal line
// passing through 0
cntHor.add(0);
// Insert vertical line
// passing through 0.
cntVer.add(0);
// Insert horizontal line
// passing through rectangle[3][0]
cntHor.add(rectangle[3][0]);
// Insert vertical line
// passing through rectangle[3][1]
cntVer.add(rectangle[3][1]);
// Insert all horizontal and
// vertical lines passing through
// the given array
for(int i = 0; i < N; i++)
{
// Insert all horizontal lines
cntHor.add(points[i][0]);
// Insert all vertical lines
cntVer.add(points[i][1]);
}
return (cntHor.size() - 1) *
(cntVer.size() - 1);
}
// Driver Code
public static void main(String args[])
{
int rectangle[][] = { { 0, 0 }, { 0, 5 },
{ 5, 0 }, { 5, 5 } };
int points[][] = { { 1, 2 }, { 3, 4 } };
int N = points.length;
System.out.println(cntRect(points, N,
rectangle));
}
}
// This code is contributed by hemanth gadarla
Python3
# Python3 program to implement # the above approach # Function to get the count # of rectangles def cntRect(points, N, rectangle): # Store distinct # horizontal lines cntHor = set([]) # Store distinct # Vertical lines cntVer = set([]) # Insert horizontal line # passing through 0 cntHor.add(0) # Insert vertical line # passing through 0. cntVer.add(0) # Insert horizontal line # passing through rectangle[3][0] cntHor.add(rectangle[3][0]) # Insert vertical line # passing through rectangle[3][1] cntVer.add(rectangle[3][1]) # Insert all horizontal and # vertical lines passing through # the given array for i in range (N): # Insert all horizontal lines cntHor.add(points[i][0]) # Insert all vertical lines cntVer.add(points[i][1]) return ((len(cntHor) - 1) * (len(cntVer) - 1)) # Driver Code if __name__ == "__main__": rectangle = [[0, 0], [0, 5], [5, 0], [5, 5]] points = [[1, 2], [3, 4]] N = len(points) print (cntRect(points, N, rectangle)) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to get the count
// of rectangles
public static int cntRect(int [,]points,
int N, int [,]rectangle)
{
// Store distinct
// horizontal lines
HashSet<int> cntHor = new HashSet<int>();
// Store distinct
// Vertical lines
HashSet<int> cntVer = new HashSet<int>();
// Insert horizontal line
// passing through 0
cntHor.Add(0);
// Insert vertical line
// passing through 0.
cntVer.Add(0);
// Insert horizontal line
// passing through rectangle[3,0]
cntHor.Add(rectangle[3, 0]);
// Insert vertical line
// passing through rectangle[3,1]
cntVer.Add(rectangle[3, 1]);
// Insert all horizontal and
// vertical lines passing through
// the given array
for(int i = 0; i < N; i++)
{
// Insert all horizontal lines
cntHor.Add(points[i, 0]);
// Insert all vertical lines
cntVer.Add(points[i, 1]);
}
return (cntHor.Count - 1) *
(cntVer.Count - 1);
}
// Driver Code
public static void Main(String []args)
{
int [,]rectangle = {{0, 0}, {0, 5},
{5, 0}, {5, 5}};
int [,]points = {{1, 2}, {3, 4}};
int N = points.GetLength(0);
Console.WriteLine(cntRect(points, N,
rectangle));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to get the count
// of rectangles
function cntRect(points, N, rectangle)
{
// Store distinct
// horizontal lines
var cntHor = new Set();
// Store distinct
// Vertical lines
var cntVer = new Set();
// Insert horizontal line
// passing through 0
cntHor.add(0);
// Insert vertical line
// passing through 0.
cntVer.add(0);
// Insert horizontal line
// passing through rectangle[3][0]
cntHor.add(rectangle[3][0]);
// Insert vertical line
// passing through rectangle[3][1]
cntVer.add(rectangle[3][1]);
// Insert all horizontal and
// vertical lines passing through
// the given array
for (var i = 0; i < N; i++) {
// Insert all horizontal lines
cntHor.add(points[i][0]);
// Insert all vertical lines
cntVer.add(points[i][1]);
}
return (cntHor.size - 1) *
(cntVer.size - 1);
}
// Driver Code
var rectangle = [[0, 0], [0, 5],
[5, 0], [5, 5]];
var points = [[1, 2], [3, 4]];
var N = points.length;
document.write( cntRect(points, N, rectangle));
// This code is contributed by noob2000.
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA