- Forum
- General C++ Programming
- Parallelogram Problem
Parallelogram Problem
Problem Description: A number (N) of lines (extending to infinity) in both directions are drawn on a plane. The lines are specified by the angle (positive or negative) made with the x axis (in degrees). It may be assumed that the different lines are not coincident (they do not overlap each other). The objective is to determine the number of parallelograms in the plane formed by these lines.
If the lines are given with an angle of 10, 70, 30 and 30
L1 is at 10 degrees to the x axis, L2 is at 70 degrees to the x axis, L3 and L4 are at 30 degrees to the x axis. It can be seen that there are no parallelograms formed by these lines
Constraints:
N<=50
-89 <= angle for any line <=90
Output:
The output is a single integer giving the number of parallelograms in the plane formed by the lines
Question: What's the easiest solution for this program?
If the lines are given with an angle of 10, 70, 30 and 30
L1 is at 10 degrees to the x axis, L2 is at 70 degrees to the x axis, L3 and L4 are at 30 degrees to the x axis. It can be seen that there are no parallelograms formed by these lines
Constraints:
N<=50
-89 <= angle for any line <=90
Output:
The output is a single integer giving the number of parallelograms in the plane formed by the lines
Question: What's the easiest solution for this program?
Presumably the whole point is for you to come up with the solution yourself. Think about it. What is a parallelogram? What kinds of relationships between the lines are needed to make one?
Consider the input 0, 0, 45, 45. Remember that the different lines are not coincident and are infinitely long. Draw it out. How many parallelograms are there? (Answer: 1)
Notice how it doesn't matter exactly where the lines are, except that the are never exactly on top of one another. Only the angles matter.
How about 0, 0, 45, 45, 70 ? (Answer: 1)
How about 0, 10, 20, 30, 40, 50, 60, 70? (Answer: 0)
How about 0, 0, 45, 45, 90, 90? (Answer: 3)
How about 0, 0, 45, 45, 90, 90, 90? (Answer: 5)
How about 0, 0, 90, 90, 90, 90, 90? (Answer: 4)
How about 0, 0, 90, 90, 90, 90, 90, 45, 45? (Answer: 9)
Consider the input 0, 0, 45, 45. Remember that the different lines are not coincident and are infinitely long. Draw it out. How many parallelograms are there? (Answer: 1)
Notice how it doesn't matter exactly where the lines are, except that the are never exactly on top of one another. Only the angles matter.
How about 0, 0, 45, 45, 70 ? (Answer: 1)
How about 0, 10, 20, 30, 40, 50, 60, 70? (Answer: 0)
How about 0, 0, 45, 45, 90, 90? (Answer: 3)
How about 0, 0, 45, 45, 90, 90, 90? (Answer: 5)
How about 0, 0, 90, 90, 90, 90, 90? (Answer: 4)
How about 0, 0, 90, 90, 90, 90, 90, 45, 45? (Answer: 9)
Last edited on
Consider the below example. What's the easiest code for this?
Example 2
Input
6
20,20,-20,-20,50,50
Output
3
Explanation
There are 6 lines (N=6) with angles 20,20, -20,-20,50 and 50 degrees with the x axis..
There are three parallelograms formed by (L1, L2, L3, L4), (L1, L2, L5, L6) and (L3, L4, L5, L6). Hence the output is 3.
Example 2
Input
6
20,20,-20,-20,50,50
Output
3
Explanation
There are 6 lines (N=6) with angles 20,20, -20,-20,50 and 50 degrees with the x axis..
There are three parallelograms formed by (L1, L2, L3, L4), (L1, L2, L5, L6) and (L3, L4, L5, L6). Hence the output is 3.
Do you see how that's exactly the same as one of my examples: 0, 0, 45, 45, 90, 90? (Answer: 3)
If you're too lazy to draw some diagrams and figure it out on your own then why should I help? Maybe someone else will do it for you but I'm not giving you any code. I'll help with any code you've written, though. Post your attempt.
If you're too lazy to draw some diagrams and figure it out on your own then why should I help? Maybe someone else will do it for you but I'm not giving you any code. I'll help with any code you've written, though. Post your attempt.
Topic archived. No new replies allowed.