计算正方形数量，可以由平行于X和Y轴的M和N条直线分别生成

原文：https://www.geeksforgeeks.org/count-squares-possible-from-m-and-n-straight-lines-parallel-to-x-and-y-axis-respectively/

给定两个数组X[]和Y[]，它们由N和M整数组成，表示平行于y轴的N条线和平行于x轴的M条线。 任务是找到在坐标平面上由这些线生成的正方形总数。

数组X[]中的每个整数（例如a）表示具有等式x = a的线，平行于y轴。 数组Y[]中的每个整数（例如b）表示具有等式y = b的线，平行于x轴。

示例：

输入：N = 3, M = 4, X[] = {1, 3, 7}, Y[] = {2, 4, 6, 1}

输出：3

说明：

3 条线平行于y轴，x = 1, x = 3, x = 7。

4 条线平行于y轴，y = 2, y = 4, y = 6, y = 1。

从上面的图像中，可以看出以下三个可能的正方形：

1）正方形CDEF（x = 1, x = 3, y = 2, y = 4），边为 2 个单位。

2）正方形ABDC（x = 1, x = 3, y = 4, y = 6），边为 2 个单位。

3）正方形BGHF（x = 3, x = 7, y = 2, y = 6），边为 4 个单位。

输入：N = 5, M = 4, X[] = {1, 9, 2, 3, 7}, Y[] = {1, 2, 4, 6}

输出：8

方法：请按照以下步骤解决问题：

  • 在X[]数组中找到所有对之间的距离，并将计数存储在映射中，例如M1。

  • 在Y[]数组中找到所有对之间的距离，并将计数存储在Map M2中。

  • 如果在M2中存在M1对的距离，则可以通过使用这两个对来生成正方形。

  • 因此，可以通过将M1以及M2中存储的所有距离计数相加来计算正方形总数。

  • 完成上述步骤后，打印正方形总数。

下面是上述方法的实现：

C++

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to count all the possible
// squares with given lines parallel
// to both the X and Y axis
int numberOfSquares(int X[], int Y[],
                    int N, int M)
{
    // Stores the count of all possible
    // distances in X[] & Y[] respectively
    unordered_map<int, int> m1, m2;
    int i, j, ans = 0;

    // Find distance between all
    // pairs in the array X[]
    for (i = 0; i < N; i++) {
        for (j = i + 1; j < N; j++) {

            int dist = abs(X[i] - X[j]);

            // Add the count to m1
            m1[dist]++;
        }
    }

    // Find distance between all
    // pairs in the array Y[]
    for (i = 0; i < M; i++) {
        for (j = i + 1; j < M; j++) {

            int dist = abs(Y[i] - Y[j]);

            // Add the count to m2
            m2[dist]++;
        }
    }

    // Find sum of m1[i] * m2[i]
    // for same distance
    for (auto i = m1.begin();
         i != m1.end(); i++) {

        // Find current count in m2
        if (m2.find(i->first)
            != m2.end()) {

            // Add to the total count
            ans += (i->second
                    * m2[i->first]);
        }
    }

    // Return the final count
    return ans;
}

// Driver Code
int main()
{
    // Given lines
    int X[] = { 1, 3, 7 };
    int Y[] = { 2, 4, 6, 1 };

    int N = sizeof(X) / sizeof(X[0]);

    int M = sizeof(Y) / sizeof(Y[0]);

    // Function Call
    cout << numberOfSquares(X, Y, N, M);

    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;

class GFG{

// Function to count all the possible
// squares with given lines parallel
// to both the X and Y axis
static int numberOfSquares(int[] X, int[] Y, int N,
                           int M)
{

    // Stores the count of all possible
    // distances in X[] & Y[] respectively
    HashMap<Integer, 
            Integer> m1 = new HashMap<Integer, 
                                      Integer>();
    HashMap<Integer, 
            Integer> m2 = new HashMap<Integer, 
                                      Integer>();

    int i, j, ans = 0;

    // Find distance between all
    // pairs in the array X[]
    for(i = 0; i < N; i++) 
    {
        for(j = i + 1; j < N; j++)
        {
            int dist = Math.abs(X[i] - X[j]);

            // Add the count to m1
            m1.put(dist, m1.getOrDefault(dist, 0) + 1);
        }
    }

    // Find distance between all
    // pairs in the array Y[]
    for(i = 0; i < M; i++) 
    {
        for(j = i + 1; j < M; j++) 
        {
            int dist = Math.abs(Y[i] - Y[j]);

            // Add the count to m2
            m2.put(dist, m2.getOrDefault(dist, 0) + 1);
        }
    }

    // Find sum of m1[i] * m2[i]
    // for same distance
    for(Map.Entry<Integer, 
                  Integer> entry : m1.entrySet())
    {

        // Find current count in m2
        if (m2.containsKey(entry.getKey()))
        {

            // Add to the total count
            ans += (entry.getValue() * 
             m2.get(entry.getKey()));
        }
    }

    // Return the final count
    return ans;
}

// Driver Code
public static void main(String[] args)
{

    // Given lines
    int X[] = { 1, 3, 7 };
    int Y[] = { 2, 4, 6, 1 };

    int N = X.length;

    int M = Y.length;

    // Function call
    System.out.println(numberOfSquares(X, Y, N, M));
}
}

// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach

# Function to count all the possible
# squares with given lines parallel
# to both the X and Y axis
def numberOfSquares(X, Y, N, M):

    # Stores the count of all possible
    # distances in X[] & Y[] respectively
    m1 = {}
    m2 = {}
    ans = 0

    # Find distance between all
    # pairs in the array X[]
    for i in range(0, N):
        for j in range(i + 1, N):
            dist = abs(X[i] - X[j])

            # Add the count to m1
            if dist in m1:
                m1[dist] = m1[dist] + 1
            else:
                m1[dist] = 1

    # Find distance between all
    # pairs in the array Y[]
    for i in range(0, M):
        for j in range(i + 1, M):
            dist = abs(Y[i] - Y[j])

            # Add the count to m2
            if dist in m2:
                m2[dist] = m2[dist] + 1
            else:
                m2[dist] = 1

    # Find sum of m1[i] * m2[i]
    # for same distance
    for key in m1:

        # Find current count in m2
        if key in m2:

            # Add to the total count
            ans = ans + (m1[key] * m2[key])

    # Return the final count
    return ans

# Driver Code
if __name__ == "__main__":

    # Given lines
    X = [ 1, 3, 7 ]
    Y = [ 2, 4, 6, 1 ]

    N = len(X)

    M = len(Y)

    # Function call
    print(numberOfSquares(X, Y, N, M))

# This code is contributed by akhilsaini

C

// C# program for the above approach
using System;
using System.Collections.Generic;

class GFG{

// Function to count all the possible
// squares with given lines parallel
// to both the X and Y axis
static int numberOfSquares(int[] X, int[] Y, int N,
                           int M)
{

    // Stores the count of all possible
    // distances in X[] & Y[] respectively
    Dictionary<int, 
               int> m1 = new Dictionary<int,
                                        int>();
      Dictionary<int, 
                 int> m2 = new Dictionary<int,
                                          int>();

    int i, j, ans = 0;

    // Find distance between all
    // pairs in the array X[]
    for(i = 0; i < N; i++)
    {
        for(j = i + 1; j < N; j++) 
        {
            int dist = Math.Abs(X[i] - X[j]);

            // Add the count to m1
              if (m1.ContainsKey(dist))
                m1[dist]++;
              else
                m1.Add(dist, 1);
        }
    }

    // Find distance between all
    // pairs in the array Y[]
    for(i = 0; i < M; i++) 
    {
        for(j = i + 1; j < M; j++) 
        {
            int dist = Math.Abs(Y[i] - Y[j]);

            // Add the count to m2
            if (m2.ContainsKey(dist))
                m2[dist]++;
              else
                m2.Add(dist, 1);
        }
    }

    // Find sum of m1[i] * m2[i]
    // for same distance
    foreach(KeyValuePair<int, int> entry in m1)
    {

        // Find current count in m2
        if (m2.ContainsKey(entry.Key))
        {

            // Add to the total count
            ans += (entry.Value * 
                 m2[entry.Key]);
        }
    }

    // Return the final count
    return ans;
}

// Driver Code
public static void Main()
{

    // Given lines
    int[] X = { 1, 3, 7 };
    int[] Y = { 2, 4, 6, 1 };

    int N = X.Length;

    int M = Y.Length;

    // Function call
    Console.WriteLine(numberOfSquares(X, Y, N, M));
}
}

// This code is contributed by akhilsaini

输出： 

3

时间复杂度：O(N ^ 2)。

辅助空间：O(n)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/33263.html