평면의 평행사변형 개수

평면 위에 서로 다른 점이 몇 개 있고 그 중 세 개가 같은 선상에 있지 않은 경우. 주어진 점으로 정점을 갖는 평행사변형의 수를 찾아야 합니다. 예:

김프의 글꼴 목록

Input : points[] = {(0 0) (0 2) (2 2) (4 2) (1 4) (3 4)} Output : 2 Two Parallelograms are possible by choosing above given point as vertices which are shown in below diagram.

평행사변형의 대각선이 중간에서 서로 교차하는 평행사변형의 특별한 성질을 이용하여 이 문제를 해결할 수 있습니다. 따라서 두 개 이상의 선분의 중간점인 중간점을 얻으면 중간점이 x번 발생하면 평행사변형이 더 정확하게 존재한다고 결론을 내릴 수 있으며 가능한 평행사변형의 대각선을 선택할 수 있습니다.^엑스기음₂즉, 주파수 x를 갖는 이 특정 중간점에 해당하는 x*(x-1)/2개의 평행사변형이 있을 것입니다. 그래서 우리는 모든 쌍의 점에 대해 반복하고 중간점을 계산하고 중간점의 빈도를 1만큼 증가시킵니다. 마지막에는 위에서 설명한 대로 각 중간점의 빈도에 따라 평행사변형의 수를 계산합니다. 중간점을 2로 나누는 빈도만 필요하므로 단순성을 위해 중간점을 계산하는 동안 무시됩니다.

CPP

// C++ program to get number of Parallelograms we // can make by given points of the plane #include    using namespace std; // Returns count of Parallelograms possible // from given points int countOfParallelograms(int x[] int y[] int N) {  // Map to store frequency of mid points  map<pair<int int> int> cnt;  for (int i=0; i<N; i++)  {  for (int j=i+1; j<N; j++)  {  // division by 2 is ignored to get  // rid of doubles  int midX = x[i] + x[j];  int midY = y[i] + y[j];  // increase the frequency of mid point  cnt[make_pair(midX midY)]++;  }  }  // Iterating through all mid points  int res = 0;  for (auto it = cnt.begin(); it != cnt.end(); it++)  {  int freq = it->second;  // Increase the count of Parallelograms by  // applying function on frequency of mid point  res += freq*(freq - 1)/2;  }  return res; } // Driver code to test above methods int main() {  int x[] = {0 0 2 4 1 3};  int y[] = {0 2 2 2 4 4};  int N = sizeof(x) / sizeof(int);  cout << countOfParallelograms(x y N) << endl;  return 0; }

Java

/*package whatever //do not write package name here */ import java.io.*; import java.util.*; public class GFG {    // Returns count of Parallelograms possible  // from given points  public static int countOfParallelograms(int[] x int[] y int N)  {  // Map to store frequency of mid points  HashMap<String Integer> cnt = new HashMap<>();  for (int i=0; i<N; i++)  {  for (int j=i+1; j<N; j++)  {  // division by 2 is ignored to get  // rid of doubles  int midX = x[i] + x[j];  int midY = y[i] + y[j];  // increase the frequency of mid point  String temp = String.join(' ' String.valueOf(midX) String.valueOf(midY));  if(cnt.containsKey(temp)){  cnt.put(temp cnt.get(temp) + 1);  }  else{  cnt.put(temp 1);  }  }  }  // Iterating through all mid points  int res = 0;  for (Map.Entry<String Integer> it : cnt.entrySet()) {  int freq = it.getValue();  // Increase the count of Parallelograms by  // applying function on frequency of mid point  res = res + freq*(freq - 1)/2;  }  return res;  }    public static void main(String[] args) {  int[] x = {0 0 2 4 1 3};  int[] y = {0 2 2 2 4 4};  int N = x.length;  System.out.println(countOfParallelograms(x y N));  } } // The code is contributed by Nidhi goel.

Python3

# python program to get number of Parallelograms we # can make by given points of the plane # Returns count of Parallelograms possible # from given points def countOfParallelograms(x y N): # Map to store frequency of mid points cnt = {} for i in range(N): for j in range(i+1 N): # division by 2 is ignored to get # rid of doubles midX = x[i] + x[j]; midY = y[i] + y[j]; # increase the frequency of mid point if ((midX midY) in cnt): cnt[(midX midY)] += 1 else: cnt[(midX midY)] = 1 # Iterating through all mid points res = 0 for key in cnt: freq = cnt[key] # Increase the count of Parallelograms by # applying function on frequency of mid point res += freq*(freq - 1)/2 return res # Driver code to test above methods x = [0 0 2 4 1 3] y = [0 2 2 2 4 4] N = len(x); print(int(countOfParallelograms(x y N))) # The code is contributed by Gautam goel.

using System; using System.Collections.Generic; public class GFG {  // Returns count of Parallelograms possible  // from given points  public static int CountOfParallelograms(int[] x int[] y int N)  {  // Map to store frequency of mid points  Dictionary<string int> cnt = new Dictionary<string int>();  for (int i = 0; i < N; i++)  {  for (int j = i + 1; j < N; j++)  {  // division by 2 is ignored to get  // rid of doubles  int midX = x[i] + x[j];  int midY = y[i] + y[j];  // increase the frequency of mid point  string temp = string.Join(' ' midX.ToString() midY.ToString());  if (cnt.ContainsKey(temp))  {  cnt[temp]++;  }  else  {  cnt.Add(temp 1);  }  }  }  // Iterating through all mid points  int res = 0;  foreach (KeyValuePair<string int> it in cnt)  {  int freq = it.Value;  // Increase the count of Parallelograms by  // applying function on frequency of mid point  res += freq * (freq - 1) / 2;  }  return res;  }  public static void Main(string[] args)  {  int[] x = { 0 0 2 4 1 3 };  int[] y = { 0 2 2 2 4 4 };  int N = x.Length;  Console.WriteLine(CountOfParallelograms(x y N));  } }

JavaScript

// JavaScript program to get number of Parallelograms we // can make by given points of the plane // Returns count of Parallelograms possible // from given points function countOfParallelograms(x y N) {  // Map to store frequency of mid points  // map int> cnt;  let cnt = new Map();  for (let i=0; i<N; i++)  {  for (let j=i+1; j<N; j++)  {  // division by 2 is ignored to get  // rid of doubles  let midX = x[i] + x[j];  let midY = y[i] + y[j];  // increase the frequency of mid point  let make_pair = [midX midY];  if(cnt.has(make_pair.join(''))){  cnt.set(make_pair.join('') cnt.get(make_pair.join('')) + 1);  }  else{  cnt.set(make_pair.join('') 1);  }  }  }  // Iterating through all mid points  let res = 0;  for (const [key value] of cnt)  {  let freq = value;  // Increase the count of Parallelograms by  // applying function on frequency of mid point  res = res + Math.floor(freq*(freq - 1)/2);  }  return res; } // Driver code to test above methods let x = [0 0 2 4 1 3]; let y = [0 2 2 2 4 4]; let N = x.length; console.log(countOfParallelograms(x y N)); // The code is contributed by Gautam goel (gautamgoel962)

산출

시간 복잡도: 에²logn) 두 개의 루프를 n까지 반복하고 logn을 사용하는 맵도 사용하기 때문입니다.
보조 공간: 에)

하드커버 vs 페이퍼백

퀴즈 만들기