平面内の平行四辺形の数

平面上に別個の点がいくつかあり、それらのうちの 3 つが同じ線上にない場合。与えられた点を頂点とする平行四辺形の数を見つける必要があります。例:

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 回出現する場合、可能な平行四辺形の対角線を次の方法で選択できれば、平行四辺形がより正確に存在すると結論付けることができます。^×C₂つまり、周波数 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) は、2 つのループを n まで反復し、logn を受け取るマップも使用しているためです。
補助スペース: の上）

クイズの作成