Last Updated on December 13, 2022 by Prepbytes
CONCEPTS USED:
Computational Geometry
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
Alex likes parallelograms very much. So one day his sister Alice gave him n numbers and asked him to calculate the count of all the parallelograms possible from the given set of points.
Help Alex calculate the total numbers of all possible parallelograms.
See original problem statement here
For Example :
Input
6
7 7
9 9
11 9
8 11
7 9
10 11
Output
2SOLVING APPROACH:
We can solve this problem by using a special property of parallelograms that diagonals of a parallelogram intersect each other in the middle. So if we get such a middle point which is middle point of more than one line segment, then we can conclude that a parallelogram exists, more accurately if a middle point occurs x times, then diagonals of possible parallelograms can be chosen in xC2 ways, i.e. there will be x*(x-1)/2 parallelograms corresponding to this particular middle point with a frequency x. So we iterate over all pair of points and we calculate their middle point and increase frequency of middle point by 1. At the end, we count number of parallelograms according to the frequency of each distinct middle point as explained above. As we just need frequency of middle point, division by 2 is ignored while calculating middle point for simplicity.
SOLUTIONS:
#include <bits/stdc++.h>
using namespace std;
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;
}
int main()
{
//write your code here
int n;cin>>n;
int x[n],y[n];
for(int i=0;i<n;i++)
cin>>x[i]>>y[i];
cout<<countOfParallelograms(x,y,n);
return 0;
}
import java.util.*;
public class Main {
static int n,p,c;
static long ans;
static Pair[] po=new Pair[2005];
static Pair[] aa=new Pair[4000005];
static class Pair implements Comparable<Pair>
{
int x,y;
Pair(int a,int b)
{
x=a;y=b;
}
public int compareTo(Pair p) {
if(x==p.x) return y-p.y;
return x-p.x;
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
n=in.nextInt();
for(int i=1;i<=n;i++)
po[i]=new Pair(in.nextInt(),in.nextInt());
Arrays.sort(po,1,n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
aa[++p]=new Pair(po[i].x-po[j].x,po[i].y-po[j].y);
Arrays.sort(aa,1,p+1);
aa[0]=new Pair(0,0);
for(int i=1;i<=p;i++)
{
if(aa[i].x==aa[i-1].x&&aa[i].y==aa[i-1].y)
{
c++;
}
else
{
ans+=(c-1)*c/2;
c=1;
}
}
ans+=(c-1)*c/2;
ans/=2;
System.out.println(ans);
}
}/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
}
}
def countOfParallelograms(x, y, N): cnt = dict() for i in range(N): for j in range(i + 1, N): midX = x[i] + x[j] midY = y[i] + y[j] if (midX, midY) in cnt: cnt[(midX, midY)] += 1 else: cnt[(midX, midY)] = 1 res = 0 for it in cnt: freq = cnt[it] res += freq * (freq - 1) // 2 return res n = int(input()) x, y =[], [] for i in range(n): a1, a2 = map(int, input().split()) x.append(a1) y.append(a2) print(countOfParallelograms(x, y, n))
[forminator_quiz id="2366"]
This article tried to discuss Computational Geometry. Hope this blog helps you understand and solve the problem. To practice more problems on Computational Geometry you can check out MYCODE | Competitive Programming.