{"id":2364,"date":"2020-07-29T07:34:01","date_gmt":"2020-07-29T07:34:01","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2364"},"modified":"2022-12-13T11:19:47","modified_gmt":"2022-12-13T11:19:47","slug":"parallelogramingpaid","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/parallelogramingpaid\/","title":{"rendered":"Parallelograming"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Computational Geometry<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

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.
\nHelp Alex calculate the total numbers of all possible parallelograms.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
Input\n6\n7 7\n9 9\n11 9\n8 11\n7 9\n10 11\n\nOutput\n2<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
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 x<\/sup>C2<\/sub> 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.<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t