Dada una array arr[][] que consta de un par de enteros que denotan coordenadas. La tarea es contar el número total de rectángulos que se pueden formar usando las coordenadas dadas.
Ejemplos:
Entrada: arr[][] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}, {11, 11} }
Salida: 3
Explicación: Los siguientes son los rectángulos formados usando las coordenadas dadas.
Primer Rectángulo (0, 0), (0, 1), (1, 0), (1, 1)
Segundo Rectángulo (0, 0), (0, 1), (2, 0), (2, 1)
Tercer Rectángulo (1, 0), (1, 1), (2, 0), (2, 1)Entrada: arr[][] = {{10, 0}, {0, 10}, {11, 11}, {0, 11}, {12, 10}}
Salida: 0
Explicación: No se pueden formar rectángulos usando estas coordenadas
Enfoque: Este problema se puede resolver usando la propiedad del rectángulo y los mapas Hash . Si se conocen dos coordenadas de un rectángulo, las otras dos coordenadas restantes se pueden determinar fácilmente. Para cada par de coordenadas, encuentre las otras dos coordenadas que pueden formar un rectángulo.
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 find number of possible rectangles
int countRectangles(vector<pair<int, int> >& ob)
{
// Creating TreeSet containing elements
set<pair<int, int> > it;
// Inserting the pairs in the set
for (int i = 0; i < ob.size(); ++i) {
it.insert(ob[i]);
}
int ans = 0;
for (int i = 0; i < ob.size(); ++i)
{
for (int j = 0; j < ob.size(); ++j)
{
if (ob[i].first != ob[j].first
&& ob[i].second != ob[j].second)
{
// Searching the pairs in the set
if (it.count({ ob[i].first, ob[j].second })
&& it.count(
{ ob[j].first, ob[i].second }))
{
// Increase the answer
++ans;
}
}
}
}
// Return the final answer
return ans / 4;
}
// Driver Code
int main()
{
int N = 7;
vector<pair<int, int> > ob(N);
// Inserting the pairs
ob[0] = { 0, 0 };
ob[1] = { 1, 0 };
ob[2] = { 1, 1 };
ob[3] = { 0, 1 };
ob[4] = { 2, 0 };
ob[5] = { 2, 1 };
ob[6] = { 11, 23 };
cout << countRectangles(ob);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program for above approach
import java.io.*;
import java.util.*;
class Main {
// Creataing pair class and
// implements comparable interface
static class Pair implements Comparable<Pair> {
int first;
int second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
// Changing sorting order of the pair class
@Override
public int compareTo(Pair o)
{
// Checking the x axis
if (this.first == o.first) {
return this.second - o.second;
}
return this.first - o.first;
}
}
// Function to find number of possible rectangles
static int countRectangles(Pair ob[])
{
// Creating TreeSet containing elements
TreeSet<Pair> it = new TreeSet<>();
// Inserting the pairs in the set
for (int i = 0; i < ob.length; ++i) {
it.add(ob[i]);
}
int ans = 0;
for (int i = 0; i < ob.length; ++i) {
for (int j = 0; j < ob.length; ++j) {
if (ob[i].first != ob[j].first
&& ob[i].second != ob[j].second) {
// Searching the pairs in the set
if (it.contains(new Pair(ob[i].first,
ob[j].second))
&& it.contains(new Pair(
ob[j].first, ob[i].second))) {
// Increase the answer
++ans;
}
}
}
}
// Return the final answer
return ans / 4;
}
// Driver Code
public static void main(String[] args)
{
int N = 7;
Pair ob[] = new Pair[N];
// Inserting the pairs
ob[0] = new Pair(0, 0);
ob[1] = new Pair(1, 0);
ob[2] = new Pair(1, 1);
ob[3] = new Pair(0, 1);
ob[4] = new Pair(2, 0);
ob[5] = new Pair(2, 1);
ob[6] = new Pair(11, 23);
System.out.print(countRectangles(ob));
}
}
Python3
# Python program for above approach
# Function to find number of possible rectangles
def countRectangles(ob):
# Creating TreeSet containing elements
it = set()
# Inserting the pairs in the set
for i in range(len(ob)):
it.add(f"{ob[i]}");
ans = 0;
for i in range(len(ob)):
for j in range(len(ob)):
if (ob[i][0] != ob[j][0] and ob[i][1] != ob[j][1]):
# Searching the pairs in the set
if (f"{[ob[i][0], ob[j][1]]}" in it and f"{[ob[j][0], ob[i][1]]}" in it):
# Increase the answer
ans += 1
# Return the final answer
return int(ans / 4);
# Driver Code
N = 7;
ob = [0] * N
# Inserting the pairs
ob[0] = [0, 0];
ob[1] = [1, 0];
ob[2] = [1, 1];
ob[3] = [0, 1];
ob[4] = [2, 0];
ob[5] = [2, 1];
ob[6] = [11, 23];
print(countRectangles(ob));
# This code is contributed by Saurabh Jaiswal
C#
// C# program for above approach
using System;
class GFG {
// Function to find number of possible rectangles.
static int countRectangles(int[, ] ob)
{
// Creating TreeSet containing elements
HashSet<KeyValuePair<int, int> > it
= new HashSet<KeyValuePair<int, int> >();
// Inserting the pairs in the set
for (int i = 0; i < ob.GetLength(0); ++i) {
it.Add(new KeyValuePair<int, int>(ob[i, 0],
ob[i, 1]));
}
int ans = 0;
for (int i = 0; i < ob.GetLength(0); ++i) {
for (int j = 0; j < ob.GetLength(0); ++j) {
if (ob[i, 0] != ob[j, 0]
&& ob[i, 1] != ob[j, 1]) {
// Searching the pairs in the set
if (it.Contains(
new KeyValuePair<int, int>(
ob[i, 0], ob[j, 1]))
&& it.Contains(
new KeyValuePair<int, int>(
ob[j, 0], ob[i, 1]))) {
// Increase the answer
ans = ans + 1;
}
}
}
}
// Return the final answer
return ans / 4;
}
static void Main()
{
int N = 7;
// Inserting the pairs
int[, ] ob
= { { 0, 0 }, { 1, 0 }, { 1, 1 }, { 0, 1 },
{ 2, 0 }, { 2, 1 }, { 11, 23 } };
Console.WriteLine(countRectangles(ob));
}
}
// The code is contributed by Gautam goel (gautamgoel962)
Javascript
<script>
// Javascript program for above approach
// Function to find number of possible rectangles
function countRectangles(ob) {
// Creating TreeSet containing elements
let it = new Set();
// Inserting the pairs in the set
for (let i = 0; i < ob.length; ++i) {
it.add(`${ob[i]}`);
}
let ans = 0;
for (let i = 0; i < ob.length; ++i) {
for (let j = 0; j < ob.length; ++j) {
if (ob[i][0] != ob[j][0]
&& ob[i][1] != ob[j][1]) {
// Searching the pairs in the set
if (it.has(`${[ob[i][0], ob[j][1]]}`)
&& it.has(`${[ob[j][0], ob[i][1]]}`)) {
// Increase the answer
++ans;
}
}
}
}
// Return the final answer
return ans / 4;
}
// Driver Code
let N = 7;
let ob = new Array(N).fill(0);
// Inserting the pairs
ob[0] = [0, 0];
ob[1] = [1, 0];
ob[2] = [1, 1];
ob[3] = [0, 1];
ob[4] = [2, 0];
ob[5] = [2, 1];
ob[6] = [11, 23];
document.write(countRectangles(ob));
// This code is contributed by Saurabh Jaiswal
</script>
3
Complejidad de tiempo: O(N 2 ), donde N es el tamaño de la array.
Espacio auxiliar: O(N), donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA